关于算法-数据结构:PAT甲级1026Table-Tennis

30次阅读

共计 7795 个字符，预计需要花费 20 分钟才能阅读完成。

题目粗心：

有 K 张乒乓球桌 (编号为 1 -K) 于 8:00 21:00 凋谢，每一组球员都是抉择以后闲暇的最小编号的球桌进行训练，且训练时长最多容许 2h, 而如果达到时没有球桌闲暇，则排成队列期待。这 K 张球桌中有 M 张是 VIP 球桌，如果存在 VIP 球桌闲暇，且期待队列中存在 VIP 球员，那么期待队列中第一个 VIP 球员将返回编号最小的 VIP 球桌训练: 如果存在 VIP 球桌闲暇，期待队列中没有 VIP 球员，那么 VIP 球桌将被调配给期待队列中第一个一般球员: 而如果以后没有 VIP 球桌闲暇，那么 VIP 球员将被看作一般球员解决。当初给出每个球员的达到工夫、须要训练时长、是否是 VIP 球员以及给出球桌数和所有 VIP 球桌编号，求所有在关门前失去训练的球员的达到工夫、训练开始工夫、期待时长以及所有球桌当天的服务人数。

解题思路：

该题目应该是 PAT_1014 和 PAT_1017 这类模仿问题中最为简单的了。对于期待队列中有非 VIP 球员和 VIP 球员，球桌中有 VIP 球桌和非 VIP 球桌，那么该问题实质上就是将球桌和球员一一对应调配的问题，思考所有的状况，简略点说就是，球座和球员的组合分为 4 种不同的状况：

  1. 第一：最早闲暇的球桌 index 是 VIP 球桌，队首球员是 VIP 球员，那么将 index 号桌子调配给他。
  2. 第二：最早闲暇的球桌 index 是 VIP 球桌，然而队首球员不是 VIP 球员，那么首先找到期待队列中第一个 VIP 球员，如果该 VIP 球员的达到工夫在 VIP 球桌闲暇之前，那么将该球桌调配给队列中的第一个 VIP 球员。如果不是，就将该 VIP 球桌调配给队首队员。
  3. 第三：最早闲暇的球桌 index 不是 VIP 球桌，然而队首球员是 VIP 球员，那么首先去查问最早闲暇的 VIP 球桌 VIPindex，如果 VIP 球员的达到工夫在 VIP 球桌闲暇工夫之后，那么将该 VIP 球桌调配给该球员。否则，就将非 VIP 球桌 index 调配给该 VIP 球员。
  4. 第四：最早闲暇的球桌 index 不是 VIP 球桌，队首球员不是 VIP 球员，那么将该球桌调配给该球员即可。

想分明下面的逻辑后接下来就是确定数据结构存储数据了，首先对于单个球员和球座都能够采纳构造体来存储数据，球员的期待队列应用 vector<Player> wait_queue 来存储，因为球桌固定了编号与之对应，那么就能够应用构造体数组来存储所有的球桌，这里为了不便实现 VIP 球员和非 VIP 球员的调配应用了 2 个期待队列别离存储 VIP 球员期待队列和非 VIP 球员的期待队列，同时应用 vip_index 和non_vip_index指向以后待处理的 VIP 球员和非 VIP 球员的地位，最初将每一个应用过球桌训练的队员应用 vector<Player> result 来存储(因为有的队员因为工夫起因无奈取得训练机会)。

算法步骤：

算法步骤：

  1. 第一步：数据的输出，依照题目要求的格局输出即可，不过得留神，对于达到工夫在完结服务工夫 end_serve_time 后的间接疏忽，同时这里对立将工夫以秒作为单位，
  2. 须要将训练时长乘以 60，并且在训练时长超过 limit_time(2h) 的时候须要将训练工夫压缩为 2h。
  3. 第二步：将期待队列中的球员依照达到工夫进行排序。
  4. 第三步：遍历期待队列，将 VIP 用户与非 VIP 用户拆散开来。
  5. 第四步：解决算法的球员与球桌匹配逻辑，循环次数为期待队列的长度.
    循环开始：首先取得队首球员，队首队员的获取是通过比拟 VIP 期待队列和非 VIP 期待队列中待处理队员谁先达到来判断的，须要留神的是有可能 VIP 期待队列或者 非 VIP 期待队列中的队员处理完毕，所以须要进行判断 (这里是该程序呈现段谬误和答案谬误的点)。而后就是 4 种状况的探讨，须要留神的是队员的等待时间有可能为 0，在队员达到的时候球桌就是闲暇的那么为 0，否则为球桌闲暇工夫减去球员的达到工夫，球桌的下场服务工夫能够对立为球桌开始服务工夫 + 队员的须要训练工夫。在程序中球员训练完结的标记就是等待时间计算结束，而后就要更新桌子的下次 闲暇工夫，并且将队员增加到result 中，将 vip_index 或non_vip_index自增。第五步：对于 result 依照服务开始的工夫进行排序，而后依照格局输入 result 中的球员的相干信息和球座的服务人数。
留神点：
  1. 期待时长是须要四舍五入到整数，也就是须要加上 30 秒再除以 60 或者应用 round 函数。
  2. table 的下标是从 1 开始的，对于从 0 开始的写法，最初会输入 3 2 3 的状况（是的题目没有说(╥╯^╰╥)）
  3. 在找到最早闲暇的桌子下标 Index 的时候得判断以后球桌的闲暇工夫是否在服务完结工夫之后，如果是那就间接退出循环，无需再进行遍历。
提交后果：

第一次提交:

测试点 1,4,5 答案谬误
测试点 3,6,7 段谬误

第二次提交：答案全对, 谬误的起因在于须要在最开始获取队首队员的时候须要判断此时还有没有待处理的 VIP 队员或者非 VIP 队员。

具体代码实现如下：
#include<cstdio>
#include<vector>
#include<algorithm>

using namespace std;

int N;// 球员数量
int K,M;// K 张桌子,M 张 VIP 桌子
int begin_serve_time = 8*3600;// 开始服务工夫
int end_serve_time = 21*3600;// 完结服务工夫
int limit_time = 2*3600;// 最长服务工夫

struct Player{
    int arriving_time;// 达到工夫
    int playing_time;// 须要服务工夫
    int waiting_time;// 等待时间
    int serve_time; // 开始服务的时刻
    bool isVIP;// 是否是 VIP
};

vector<Player> wait_queue;// 期待队列
int vip_index = 0;// 期待队列工作指针，指向第一个待处理的 VIP 用户
int non_vip_index = 0;// 期待队列工作指针，指向第一个待处理的非 VIP 用户
vector<Player> vip_wait_queue;//VIP 期待队列
vector<Player> non_vip_wait_queue;// 非 VIP 用户期待队列
vector<Player> result;// 依照解决完结的程序保留每一个曾经解决的队员


struct Table{
    int begin_time = begin_serve_time;// 开始服务工夫
    int number;// 服务的球员数目
    bool isVIP;// 是否是 VIP 桌子
}table[110];

int getTime(int hh,int mm,int ss){return hh*3600+mm*60+ss;}

bool cmpByArriveTime(Player a,Player b){return a.arriving_time<b.arriving_time;}

bool cmpByServeTime(Player a,Player b){return a.serve_time<b.serve_time;}

int main(){scanf("%d",&N);
    for(int i=0;i<N;++i){
        int hh,mm,ss,time,vip;
        scanf("%d:%d:%d %d %d",&hh,&mm,&ss,&time,&vip);
        int arrive_time = getTime(hh,mm,ss);
        if(arrive_time<end_serve_time){
            Player player;
            // 在完结服务之前达到
            player.arriving_time = arrive_time;
            // 最长服务工夫是 2 小时
            player.playing_time = time*60>limit_time?limit_time:time*60;
            player.isVIP = vip == 1;
            wait_queue.push_back(player);
        }
    }
    scanf("%d %d",&K,&M);
    // 标记 VIP 桌子
    for(int i=0;i<M;++i){
        int index;
        scanf("%d",&index);
        table[index].isVIP = true;
    }
    int n = wait_queue.size();
    // 依照达到工夫进行排序
    sort(wait_queue.begin(),wait_queue.end(),cmpByArriveTime);
    // 将 VIP 用户与非 VIP 用户拆散开来
    for(int i=0;i<n;++i){if(wait_queue[i].isVIP){vip_wait_queue.push_back(wait_queue[i]);
        }else{non_vip_wait_queue.push_back(wait_queue[i]);
        }
    }
    int vip_number = vip_wait_queue.size();
    int non_vip_number = non_vip_wait_queue.size();
    // 解决 n 个用户
    for(int i=0;i<n;++i){
        // 第二次提交批改的代码局部：// 队首球员
        bool flag;// 判断队首球员是否是 VIP 球员
        if(vip_index<vip_number&&non_vip_index<non_vip_number){
            // VIP 队员和非 VIP 队员都存在，抉择先达到的作为队首队员
            flag = vip_wait_queue[vip_index].arriving_time < non_vip_wait_queue[non_vip_index].arriving_time;
        }else {
            // 存在 VIP 队员就是 true, 没有就是 false
            flag = vip_index < vip_number;
        }
        // 队首队员
        Player player = flag ? vip_wait_queue[vip_index] : non_vip_wait_queue[non_vip_index];
        // 首先找到服务工夫最早完结并且编号最小的桌子
        int minTime = 0x3fffffff;
        int index;
        for(int j=1;j<=K;++j){if(minTime>table[j].begin_time){minTime = table[j].begin_time;
                index = j;
            }
        }
        if(minTime>=end_serve_time){
            // 最早服务完结的桌子在 21 点当前就不进行服务了
            break;
        }
        if(table[index].isVIP){
            // 如果是 VIP 桌子
            if(player.isVIP){
                // 队首球员也是 VIP, 将该 VIP 球座调配给 VIP 球员
                if(table[index].begin_time>=player.arriving_time){
                    // 球员到的时候球桌还没有闲暇
                    player.waiting_time = table[index].begin_time - player.arriving_time;
                    player.serve_time = table[index].begin_time; // 更新球员的开始服务工夫
                }else{
                    // 球员到的时候球桌曾经闲暇，没有等待时间, 开始服务工夫就是达到工夫
                    player.waiting_time = 0;
                    player.serve_time = player.arriving_time;// 球员开始服务工夫就是球员达到工夫
                }
                table[index].begin_time = player.serve_time + player.playing_time;// 更新该桌子的开始服务工夫
                ++table[index].number;// 累计该桌子为用户提供服务的人数
                result.push_back(player);
                // 队首球员是 VIP
                ++vip_index;
            }else{
                // 队首球员不是 VIP，判断第一个 VIP 球员是否在球座闲暇之前达到。if(vip_index<vip_number&&vip_wait_queue[vip_index].arriving_time<=table[index].begin_time){
                    // 在闲暇前达到, 调配给该 VIP 球员.
                    vip_wait_queue[vip_index].waiting_time = table[index].begin_time - vip_wait_queue[vip_index].arriving_time;
                    vip_wait_queue[vip_index].serve_time = table[index].begin_time;
                    table[index].begin_time += vip_wait_queue[vip_index].playing_time;// 更新该桌子的开始服务工夫
                    ++table[index].number;// 累计该桌子为用户提供服务的人数
                    result.push_back(vip_wait_queue[vip_index]);
                    ++vip_index;
                }else{
                    // 没有 VIP 球员或者不在桌子闲暇前达到，调配给队首球员
                    if(table[index].begin_time>=player.arriving_time){
                        // 球员到的时候球桌还没有闲暇
                        player.waiting_time = table[index].begin_time - player.arriving_time;
                        player.serve_time = table[index].begin_time; // 更新球员的开始服务工夫
                    }else{
                        // 球员到的时候球桌曾经闲暇，没有等待时间, 开始服务工夫就是达到工夫
                        player.waiting_time = 0;
                        player.serve_time = player.arriving_time;// 球员开始服务工夫就是球员达到工夫
                    }
                    table[index].begin_time = player.serve_time + player.playing_time;// 更新该桌子的开始服务工夫
                    ++table[index].number;// 累计该桌子为用户提供服务的人数
                    result.push_back(player);
                    // 队首球员不是 VIP
                    ++non_vip_index;
                }
            }
        }else {
            // 桌子不是 VIP
            if(player.isVIP){
                // 队首球员是 VIP，查找最早闲暇的 VIP 球座
                minTime = 0x3fffffff;
                int vipIndex = -1;
                for(int j=1;j<=K;++j){if(minTime>table[j].begin_time&&table[j].isVIP){minTime = table[j].begin_time;
                        vipIndex = j;
                    }
                }
                if(vipIndex!=-1&&table[vipIndex].begin_time<=player.arriving_time){
                    // 找到一张 VIP 桌子并且在队首球员达到之后就是闲暇的，将该 VIP 球桌调配给队首球员
                    player.waiting_time = 0;// 没有等待时间
                    player.serve_time = player.arriving_time;// 开始服务工夫就是达到工夫
                    table[vipIndex].begin_time = player.serve_time + player.playing_time;// 更新该桌子的下次服务工夫
                    ++table[vipIndex].number;
                    result.push_back(player);
                    // 队首球员是 VIP
                    ++vip_index;
                }else {
                    // 没有 VIP 桌子或者队首球员达到时没有闲暇，将 index 非 VIP 桌子调配给队首球员
                    if(table[index].begin_time>=player.arriving_time){
                        // 球员到的时候球桌还没有闲暇
                        player.waiting_time = table[index].begin_time - player.arriving_time;
                        player.serve_time = table[index].begin_time; // 更新球员的开始服务工夫
                    }else{
                        // 球员到的时候球桌曾经闲暇，没有等待时间, 开始服务工夫就是达到工夫
                        player.waiting_time = 0;
                        player.serve_time = player.arriving_time;// 球员开始服务工夫就是球员达到工夫
                    }
                    table[index].begin_time = player.serve_time + player.playing_time;// 更新该桌子的开始服务工夫
                    ++table[index].number;// 累计该桌子为用户提供服务的人数
                    result.push_back(player);
                    // 队首球员是 VIP
                    ++vip_index;
                }
            }else {
                // 球员不是 VIP，间接将该桌子调配给该球员
                if(table[index].begin_time>=player.arriving_time){
                    // 球员到的时候球桌还没有闲暇
                    player.waiting_time = table[index].begin_time - player.arriving_time;
                    player.serve_time = table[index].begin_time; // 更新球员的开始服务工夫
                }else{
                    // 球员到的时候球桌曾经闲暇，没有等待时间, 开始服务工夫就是达到工夫
                    player.waiting_time = 0;
                    player.serve_time = player.arriving_time;// 球员开始服务工夫就是球员达到工夫
                }
                table[index].begin_time = player.serve_time + player.playing_time;// 更新该桌子的开始服务工夫
                ++table[index].number;// 累计该桌子为用户提供服务的人数
                result.push_back(player);
                // 队首球员不是 VIP
                ++non_vip_index;
            }
        }
    }
    // 依据开始服务的工夫进行排序
    sort(result.begin(),result.end(),cmpByServeTime);
    // 输入每一个用户的达到工夫，开始服务工夫和等待时间
    int r = result.size();
    for(int i=0;i<r;++i){printf("%02d:%02d:%02d %02d:%02d:%02d %d\n",result[i].arriving_time/3600,result[i].arriving_time%3600/60,result[i].arriving_time%60,
               result[i].serve_time/3600,result[i].serve_time%3600/60,result[i].serve_time%60,
               (result[i].waiting_time+30)/60);
    }
    // 输入每一张桌子服务的人数
    for(int i=1;i<=K;++i){printf("%d",table[i].number);
        if(i<K) printf(" ");
    }
    return 0;
}

正文完
算法-数据结构
发表至： 算法-数据结构
2020-09-21
 0
关于算法-数据结构:面向-offer-学算法笔面试大杀器-单调栈
关于算法-数据结构:PAT甲级1078-Hashing
关于算法-数据结构:Leetcode-322-零钱兑换
关于算法-数据结构:PAT甲级1140-Lookandsay-Sequence