[PAT解题报告] Waiting in Line
这种题目叫做模拟题——意思是说，没什么算法，题目给定规则，让你模拟一个事件。规则很细致，往往很容易出错。
例如本题，有如下几条规则：
（1） 所有人是按照顺序到来的，可以认为他们都在等候，每个人要办的服务的时间给定，是p[i]。
（2） 有n个窗口队列，每个队列长度不能超过m。多余的人只能在外面等候——还不能选择窗口。
（3） 如果允许，每个人会选择最短的队列进入，如果很多队列都是最短的，选取编号较小的。
（4） 真正服务开始的时间是8点，结束时间是17点。
输出的是一些人最终业务办理完成的时间。
解决： 我们直接模拟，对每个队列记录入队的人的id。
对每个人试图选一个队列入队，一旦入队，我们就能知道他开始服务的时间（是当前时间或者前一个人服务结束的时间），以及他业务办理完成的时间——开始时间加上处理时间。
一旦一个人无法入队——所有队伍全满，我们试图出队，把所有队头的业务办理完成时间最小的（多个）出队即可，同时更新当前时间为这个时间。
实际上是从时间轴上考虑谁能入队，谁能出队。结束条件是所有人都入队，并不需要都出队，因为入队时我们已经能计算出他的业务办理完成时间了。最终输出注意8点和17点的限制就好了。
代码：
#include <string>
#include <deque>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
deque<int> q[22];
int answer[1002],start[1002];
int p[1002];
const int t8 = 8 * 60;
const int t17 = 17 * 60;
int main() {
int n,m,k,t;
scanf("%d%d%d%d",&n,&m,&k,&t);
for (int i = 0; i < k; ++i) {
scanf("%d", p + i);
}
for (int now = t8, id = 0;;) {
for (;id < k;++id) {
int x = 0;
for (int i = 0; i < n; ++i) {
if (q[i].size() < q[x].size()) {
x = i;
}
}
if (q[x].size() >= m) {
break;
}
answer[id] = (start[id] = q[x].empty()?now:answer[q[x].back()]) + p[id];
q[x].push_back(id);
}
if (id >= k) {
break;
}
now = answer[q[0].front()];
for (int i = 0; i < n; ++i) {
now = min(now, answer[q[i].front()]);
}
for (int i = 0; i < n; ++i) {
if (answer[q[i].front()] == now) {
q[i].pop_front();
}
}
}
for (;t;--t) {
int x;
scanf("%d",&x);
if (start[--x] >= t17) {
puts("Sorry");
}
else {
printf("%02d:%02d\n",answer[x] / 60, answer[x] % 60);
}
}
return 0;
}
原题链接：http://www.patest.cn/contests/pat-a-practise/1014
网易有道公司氛围 38人发布
投递美团等公司10个岗位 >