本文转载自微信公众号“吹笛蛋窝”，作者吹笛蛋。转载本文请联系派珀蛋巢公众号。一道PAT原题，号称“PAT史上最头疼的一道题”：PAT原题英文链接：https://pintia.cn/problem-sets/994805342720868352/problems/994805472333250560AcWing翻译：https://www.acwing.com/problem/content/1505/原题某乒乓球俱乐部有K张乒乓球台，编号为1~K。对于任何一对玩家，如果他们到达时有超过一张桌子可用，他们将被分配到号码较小的桌子上。如果所有的桌子都被占用，他们将不得不排队等候。假设每对玩家最多只能玩两个小时。你需要计算每个人排队等候的时间，以及当天每张牌桌上有多少对玩家。此外，更复杂的是，俱乐部为VIP玩家预留了一些桌子。当贵宾桌出现空位时，等候队伍中的第一对贵宾玩家将优先使用该桌。如果此时队列中没有贵宾，队列中的第一对玩家可以使用桌子。另一方面，当轮到VIP对玩时，如果没有VIP桌可用，他们将被视为普通玩家。补充说明：1、当等待队列中有VIP玩家且有空闲VIP桌时，必须先分配VIP玩家，分配其VIP桌（人数少者优先）直到所有VIP用户或分配贵宾桌。2.预计游玩两小时以上者，只允许游玩两小时。3、当多对玩家同时开始游戏时，输出到达时间较早的玩家信息。4.当等待的玩家中没有VIP时，VIP桌将按普通桌处理。当可用牌桌中没有VIP牌桌时，VIP玩家将被视为普通玩家。输入格式的第一行包含一个整数N，表示有N对玩家。接下来N行，每行包含两次时间和一个VIPID，HH:MM:SS--到达时间，p--播放时间（单位：分钟），tag--如果是，说明这是一对VIP，如果所以，这意味着他们不是贵宾。保证抵达时间为08:00:00至21:00:00，这是俱乐部的营业时间。保证每对玩家在不同的时间到达。另一行包含两个整数K和M，表示表数和VIP表数。最后一行有M个整数，代表贵宾桌的编号。输出格式首先输出每对玩家的到达时间、开始播放时间和等待时间。每对选手的信息占一行，按照开始时间从早到晚的顺序依次输出。等待时间必须四舍五入到整分钟。如果一对玩家直到21:00:00（不包括21:00:00）才拿到桌子，则不需要输出他们的信息。输出另一行，K个整数，代表每桌服务的玩家对数。数据范围输入示例：920:52:0010008:00:0020008:02:0030020:51:0010008:10:005008:12:0010120:50:0010008:01:3015120:53:00101312输出样例：08:00:0008:00:00008:01:3008:01:30008:02:0008:02:00008:12:0008:16:30508:10:0008:20:001020:50:0020:50:00020:51:0020:51:00020:52:0020:52:0003321026表网球(30point(s))一个乒乓球俱乐部有N张桌子可供公众使用。桌子编号从1到N。对于任何一对玩家，如果他们到达时有一些桌子开放，他们将被分配到编号最小的可用桌子。如果所有的桌子都被占用，他们将不得不排队等候。假设每对玩家最多可以玩2小时。你的工作是计算每个排队的人的等待时间，并计算每张桌子当天服务的玩家数量。使这个程序成为可能的一件事有点复杂的是俱乐部为他们的VIP会员预留了一些桌子。当一个VIP桌开放，队列中的第一对VIP将有特权拿走它。但是，如果队列中没有VIP，下一对玩家可以拿。另一方面，如果轮到VIP对时，没有VIP表可用，则可以像任何普通玩家一样分配他们。输入说明：每个输入文件包含一个测试用例。对于每种情况，第一行包含一个整数N（≤10000）-玩家对的总数。然后是N行，每行包含2次和一个VIP标签：HH:MM:SS-到达时间，P-一对玩家的游戏时间，以分钟为单位，标签-如果他们持有VIP卡，则为1，如果不是，则为0。俱乐部开放期间，保证抵达时间为08:00:00至21:00:00。假设没有两个顾客同时到达。玩家信息后面有2个正整数：K(≤100)-牌桌数，M(#include#include#include#include#includeusingnamespacestd;constintN=1e4+10,M=1e2+10,INF=2e9;intn,k,m;structPlayer{intarrive_time,serve_time;intstart_time,waiting_time;//排序行constbooloperator<(constPlayer&t)const{if(start_time!=t.start_time)returnstart_time(constPlayer&t)const{returnarrive_time>t.arrive_time;}};structTable{intid;intend_time;constbooloperator>(constTable&t)const{if(end_time!=t.end_time)returnend_time>t.end_time;returnid>t.id;}};boolis_vip_table[M];inttable_count[M];//玩家最终输出andSequencevectorplayers;//注意`&`很重要voidassign(priority_queue,greater>&ps,priority_queue,greater>&ts){autop=ps.top();ps.pop();autot=ts.top();ts.pop();intstart_time=t.end_time;intend_time=start_time+p.serve_time;ts.push({t.id,end_time});table_count[t.id]++;p.start_time=start_time;p.waiting_time=round((start_time-p.arrive_time)/60.0);players.push_back(p);}stringtime_to_string(intsec){charstr[20];sprintf(str,"%02d:%02d:%02d",sec/?0,sec%?0/60,sec%60);returnstr;}intmain(){//输入玩家priority_queue,greater>normal_players;priority_queue,greater>vip_players;normal_players.push({INF});vip_players.push({INF});cin>>n;for(inti=0;i,greater>normal_tables;priority_queue,greater>vip_tables;normal_tables.push({-1,INF});vip_tables.push({-1,INF});cin>>k>>m;for(inti=0;i>id;is_vip_table[id]=true;}for(inti=1;i<=k;i++){if(is_vip_table[i])vip_tables.push({i,8*3600});elsenormal_tables.push({i,8*3600});}//开始分配while(normal_players.size()>1||vip_players.size()>1){autonp=normal_players.top();autovp=vip_players.top();intcur_time=min(np.arrive_time,vp.arrive_time);while(normal_tables.top().end_time=21*3600)break;if(vp.arrive_time<=end_time&&vt.end_time==end_time)assign(vip_players,vip_tables);elseif(np.arrive_timevt)assign(normal_players,vip_tables);elseassign(normal_players,normal_tables);}else{if(nt>vt)assign(vip_players,vip_tables);elseassign(vip_players,normal_tables);}}sort(players.begin(),players.end());for(autop:players){cout<
