PAT甲级1026 Table Tennis (30分)|C++实现
一、题目描述
原题链接
A table tennis club has N tables available to the public. The tables are numbered from 1 to N. For any pair of players, if there are some tables open when they arrive, they will be assigned to the available table with the smallest number. If all the tables are occupied, they will have to wait in a queue. It is assumed that every pair of players can play for at most 2 hours.
Your job is to count for everyone in queue their waiting time, and for each table the number of players it has served for the day.
One thing that makes this procedure a bit complicated is that the club reserves some tables for their VIP members. When a VIP table is open, the first VIP pair in the queue will have the privilege to take it. However, if there is no VIP in the queue, the next pair of players can take it. On the other hand, if when it is the turn of a VIP pair, yet no VIP table is available, they can be assigned as any ordinary players.
Input Specification:
Output Specification:
Sample Input:
9
20:52:00 10 0
08:00:00 20 0
08:02:00 30 0
20:51:00 10 0
08:10:00 5 0
08:12:00 10 1
20:50:00 10 0
08:01:30 15 1
20:53:00 10 1
3 1
2
Sample Output:
08:00:00 08:00:00 0
08:01:30 08:01:30 0
08:02:00 08:02:00 0
08:12:00 08:16:30 5
08:10:00 08:20:00 10
20:50:00 20:50:00 0
20:51:00 20:51:00 0
20:52:00 20:52:00 0
3 3 2
二、解题思路
是一道大模拟题，有点复杂，里面也有一些小坑。
首先，题目给出一堆杂乱的信息，是用户到达的时间、服务时间以及是不是vip。要求我们按开始服务的时间顺序输出每个客户的到达时间，开始服务时间以及等待时间，最后一行输出每个桌子所服务的客户数。
很容易想到的是，我们可以把每个（对）客户设置成一个结构体，包括到达时间，服务时长，开始时间，等待时间以及是否为vip，是否已经安排桌子。用一个结构体vector存放所有客户，随后按照到达时间进行排序。 接下来遍历所有客户，对于每个客户，我们遍历一遍所有窗口，找出最早空闲的那个，如果这个桌子是vip预留桌，遍历一次客户，寻找有没有能插队使用的vip，如果没有，我们就再次遍历所有客户，找出第一个可以使用该桌子的用户，但是这个用户也有可能是vip（注意这里为什么不和前一个一起操作，是因为会存在处理到vip用户，但是已经有两个桌子空闲，vip用户会优先去vip预留桌而不是另一个桌子），所以我们在这里也要进行一次操作，最后才是对普通用户的操作。
细节都在代码注释中，这个代码自认为写得很烂，但是暂时没有什么更好的思路，还是得多读读别人的代码，了解他们的思路。
三、AC代码
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxtable = 101; //据题意桌子的数量不会大于100
const int INF = 10000000; //设置INF
int endT[maxtable]; //表示每个桌子的最早空闲时间
int cntT[maxtable] = {0}; //表示每个桌子服务的顾客数（pairs）
bool vTable[maxtable] = {false}; //标记每个桌子是否为vip预留桌
struct people
{
int arrive, serve, beginTime, wait; //到达时间，服务时长，开始时间，等待时间
bool V, checked = false; //是否为vip，是否已经安排桌子
};
bool cmp1(people a, people b)
{return a.arrive < b.arrive;} //按到达时间排队
int change(int h, int m, int s) //所有时间化为秒制
{return h*3600 + m*60 + s;}
int main()
{
int stTime = change(8, 0, 0), edTime = change(21, 0, 0); //开门关门时间
int N, K, M, h1, m1, s1, servetime, v;
bool vipIsHere = true; //队伍里有vip
people tmp; //临时变量
vector<people> ord; //所有排队的人
scanf("%d", &N); //人数
for(int i=0; i<N; i++)
{
scanf("%d:%d:%d %d %d", &h1, &m1, &s1, &servetime, &v);
tmp.arrive = change(h1, m1, s1);
if(servetime > 120) servetime = 120; //最长服务时间为2小时
tmp.serve = servetime*60; //化为秒制
tmp.V = v ? true : false; //标记是否vip
ord.push_back(tmp); //存入vector
}
int mk; //临时输入变量
scanf("%d%d", &K, &M); //输入桌子数目以及vip预留桌数目
for(int i=0; i<M; i++)
{
scanf("%d", &mk);
vTable[mk] = true; //标记vip预留桌
}
for(int i=1; i<=K; i++) endT[i] = stTime; //初始化每个桌子的最早空闲时间
sort(ord.begin(), ord.end(), cmp1); //对到达的用户按照到达时间进行排队
int sze = ord.size(); //总人数
vector<people> ans; //表示有效人数
for(int i=0; i<sze; i++)
{
int idx = -1, minEnd = INF; //标记最早结束的桌子，最早结束时间
bool done = false;
for(int j=1; j<=K; j++) //查找最早结束的桌子以及时间
{
if(endT[j] < minEnd)
{
minEnd = endT[j];
idx = j;
}
}
if(minEnd >= edTime) break; //有桌子空闲时已经关门，不接待用户，后面的数据可以忽略
if(vTable[idx] && vipIsHere) //该空闲桌子是vip预留桌且队伍中有vip
{
int k;
for(k=0; k<sze; k++) //查找vip
{
if(ord[k].V && !ord[k].checked) //有vip且还未分配桌子
{
if(ord[k].arrive <= endT[idx]) //该vip到达时间比空闲时间更早
{
ord[k].beginTime = endT[idx]; //更新开始使用乒乓桌的时间
ord[k].wait = ord[k].beginTime - ord[k].arrive; //更新等待时间
endT[idx] += ord[k].serve; //更新桌子最早空闲时间
ord[k].checked = true; //已经安排过桌子了
if(ord[k].beginTime < edTime) //如果开始时间比关门时间更晚，不予处理
{
ans.push_back(ord[k]); //有效客户
cntT[idx]++; //桌子的用户数+1
}
done = true; //标志该桌子已经给vip用户使用
break;
}
else break;
}
}
if(k == sze) vipIsHere = false; //遍历完了也没有vip
}
if(!done) //该桌子没有给vip使用
{
for(int l=0; l<sze; l++) //遍历所有客户
{
if(!ord[l].checked) //找到第一个还没有安排桌子的客户
{
if(ord[l].V) //如果这个客户是vip
{
int m;
for(m=1; m<=K; m++) //遍历所有桌子
{
if(ord[l].arrive >= endT[m] && vTable[m]) //他到达的时候已经有多个桌子空出来，会优先去vip预留桌
{
ord[l].beginTime = ord[l].arrive;
ord[l].wait = ord[l].beginTime - ord[l].arrive;
endT[m] = ord[l].beginTime + ord[l].serve;
ord[l].checked = true;
if(ord[l].beginTime < edTime)
{
ans.push_back(ord[l]);
cntT[m]++;
}
break;
}
}
if(m != K+1) break; //如果已经有符合要求的桌子出现，退出循环
}
//处理正常客户
ord[l].beginTime = max(ord[l].arrive, endT[idx]);
ord[l].wait = ord[l].beginTime - ord[l].arrive;
endT[idx] = ord[l].beginTime + ord[l].serve;
ord[l].checked = true;
if(ord[l].beginTime < edTime)
{
ans.push_back(ord[l]);
cntT[idx]++;
}
break;
}
}
}
}
int sze2 = ans.size();
for(int i=0; i<sze2; i++) //开始进行输出操作
{
int h1, h2, m1, m2, s1, s2;
double waitTime;
h1 = ans[i].arrive / 3600;
m1 = ans[i].arrive % 3600 / 60;
s1 = ans[i].arrive % 60;
h2 = ans[i].beginTime / 3600;
m2 = ans[i].beginTime % 3600 / 60;
s2 = ans[i].beginTime % 60;
waitTime = ans[i].wait / 60.0;
printf("%02d:%02d:%02d %02d:%02d:%02d %0.0f\n", h1, m1, s1, h2, m2, s2, round(waitTime));
}
for(int i=1; i<=K; i++)
{
if(i==1) printf("%d", cntT[i]);
else printf(" %d", cntT[i]);
}
return 0;
}