乐趣区

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

作者：

jiezi

在

题目粗心：

有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;
}

评论

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

这个站点使用 Akismet 来减少垃圾评论。了解你的评论数据如何被处理。

更多文章