题目大意:银行有N个窗口,每个窗口最多排队M个人。假设有K个人都从8:00开始等待办理业务,并给出处理每个人业务的时间。前 N * M个人依次在N个窗口前排队,后面的人按照顺序,只有在某个窗口有空出位置时(人数小于M时),到该窗口排队。如果有多个窗口同时空出,选择序号小的。求出每个人结束业务的时间,注意如果某个人在17:00前还没有开始办理业务的话,他就不能办理业务了。
用N个队列 queue<int> q[N] 表示窗口,首先将 min(N*M, K)个人按顺序放到这N个队列里,每个队列的pop时间即为队首元素需要处理业务的时间。对于剩下的 K - N*M 个人,依次处理。首先找到最早空出的窗口,然后将该队列pop,再push正在处理的人,然后更新该队列的pop时间。
不过这样存在的问题是最后加入队列的人的开始时间没法更新,为了方便起见,另外设置N个队列 queue<int> calTime[N] ,进行相同的push操作,而不进行pop操作。这样当所有人处理完毕后,calTime[N] 就完整地存储了所有人所在的队列信息。计算时间用 calTime[N] 即可。
AC代码如下:
#include <iostream>
#include <vector>
#include <cstdio>
#include <queue>
using namespace std;
const int MAXN = 21;
queue<int> q[MAXN];
queue<int> calTime[MAXN];
int popTime[MAXN] = {0};
void printTime(int startTime, int needTime)
{
if(startTime >= (17 - 8) * 60) printf("Sorry\n");
else
{
int hour = 8 + (startTime + needTime) / 60;
int min = (startTime + needTime) % 60;
printf("%02d:%02d\n", hour, min);
}
}
int main()
{
int N, M, K, Q;
cin >> N >> M >> K >> Q;
vector<int> needTime(K);
vector<int> serveTime(K);
for (int i = 0; i < K; ++i)
{
scanf("%d", &needTime[i]);
}
for (int i = 0; i < N * M && i < K; ++i)
{
q[i % N].push(i);
calTime[i % N].push(i);
if(q[i % N].size() == 1) popTime[i % N] += needTime[q[i % N].front()];
}
for (int i = N * M ; i < K; ++i)
{
int minIndex = 0, minTime = 0x7FFFFFFF;
for (int j = 0; j < N; ++j)
{
if(popTime[j] < minTime)
{
minTime = popTime[j];
minIndex = j;
}
}
q[minIndex].pop();
q[minIndex].push(i);
calTime[minIndex].push(i);
popTime[minIndex] += needTime[q[minIndex].front()];
}
for (int i = 0; i < N; ++i)
{
int end = 0;
while(!calTime[i].empty())
{
serveTime[calTime[i].front()] = end;
end += needTime[calTime[i].front()];
calTime[i].pop();
}
}
for (int query = 0; query < Q; ++query)
{
int index;
scanf("%d", &index);
index--;
printTime(serveTime[index], needTime[index]);
}
return 0;
}