[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