[PAT-A 1014]Waiting in Line
银行处共有N个服务窗口，在黄线外依次排列等待的客户数量有限制M人（即每个窗口前最多可容纳M位顾客排队）。现有K位客户需要依次接受服务操作，并假设每位客户的平均处理时间为已知数据。所有客户均于8:00整按编号顺序到达黄线外等候，并且当任意一个窗口处当前已有的队伍未满（即未达到M人）时，在黄线外第一个到达的客户将选择当前队列人数最少的那个窗口加入排队序列；若此时多个队列长度相同，则选择队列序号较小的那个窗口进行加入。针对Q个特定的客户编号进行查询操作：对于每一个指定的客户编号返回该客户的最终服务完成时间；若某客户在17:00时仍未完成服务，则放弃其服务请求；无论其所需服务时长多长均会为其提供完整的处理时间支持。
思路：
1.当一位客户进入某一窗口队列时，他的服务时间就已经确定了，即当前在该窗口排队的所有人的服务时间之和，而在所有窗口排满后，剩余客户能够去排队的时间点时所有窗口最找结束的队首客户，也就是说，在所有窗口排满的情况下，每当有一个窗口的队首客户结束服务，（结束时间相同，窗口ID小的视为先结束），剩余客户的第一个就会排到那个窗口的最后面。
可以建立一个窗口结构体window，存放当前队伍的最后服务时间endTime和队首客户的服务结束时间popTime，并维护一个该窗口排队的队列q。
2.在8：00前，只要窗口的队列没满，就把客户按照窗口编号0，1，2，…，n-1，0，1，2…n-1循环入队，且在安排的过程中不断的更新窗口的endTime和popTime，其中endTime将直接刚入队的客户的服务结束时间保存下来，而popTime尽在安排每个窗口的第一客户实时更新。
3.如果步骤2已经将所有的窗口都排满，那么在该步中将剩下的客户入队，由于所有的窗口排满的情况下，每当又一个窗口的队首客户结束服务（结束时间相同，ID小的视为先结束），剩余客户的第一个就会排到那个客户后面，对每一个这样的客户，可以选择当前所有窗口中popTime中最小的窗口，popTime相同选择ID较小的，将客户排到该窗口的队列后面，并更新该窗口的endTime和popTime，其中endTime作为刚入队的客户的服务结束时间保存。
4.对每一个输入的查询客户编号，如果他的服务开始时间在17：00之后(含17：00)，则输出sorry，否则，输出他的服务结束时间。
5.把所有的时间转换为分钟，以便时间的处理与比较。
AC代码：
//PAT_A 1014
#include<cstdio>
#include<queue>
#include<algorithm>
using namespace std;
const int maxn = 1111;
int convertTime(int hh, int mm) {
return hh * 60 + mm;
}
struct Window {
int endTime, popTime;//最后一个客户结束服务的时间，队首客户结束服务的时间
queue<int> q;//这个窗口的排队队列
}window[20];
int ans[maxn], need[maxn];//每个客户的结束时间与需要时间
int main() {
int n, m, k, query, q, inIndex = 0;
(void)scanf("%d %d %d %d", &n, &m, &k, &query);
for (int i = 0; i < k; i++) {
(void)scanf("%d", &need[i]);
}
for (int i = 0; i < n; i++) {
window[i].popTime = window[i].endTime = convertTime(8, 0);//初始时间设在8点
}
for (int i = 0; i < min((n * m), k); i++) {
window[inIndex % n].q.push(inIndex);
window[inIndex % n].endTime += need[inIndex];
if (inIndex < n)window[inIndex].popTime += need[inIndex];//窗口第一个客户
ans[inIndex] = window[inIndex % n].endTime;//答案保存为当前队列结束时间
inIndex++;
}
for (; inIndex < k; inIndex++) {
int idx = -1, minPopTime = 1 << 30;
for (int i = 0; i < n; i++) {
if (window[i].popTime < minPopTime) {
minPopTime = window[i].popTime;
idx = i;
}
}
window[idx].q.pop();
window[idx].q.push(inIndex);
window[idx].endTime += need[inIndex];
window[idx].popTime += need[window[idx].q.front()];
ans[inIndex] += window[idx].endTime;
}
for (int i = 0; i < query; i++) {
(void)scanf("%d", &q);
if (ans[q - 1] - need[q - 1] >= convertTime(17, 0))printf("Sorry\n");//在17：00之后才能服务
else printf("%02d:%02d\n", ans[q - 1] / 60, ans[q - 1] % 60);
}
return 0;
}