[PAT解题报告] Queueing at Bank
一个银行有K个窗口，每个窗口只能服务一个人，有n个人，达到时间不同，银行开始服务和结束服务的时间是8点到17点，如果17点前到达，但是在排队，最后服务的时间比17点晚是可能的，但是17点以后到达的人就没办法了。给定每个人达到时间和服务的时间，求办理业务的人的平均等待时间。
分析：
这个也是模拟题。其实我们不关心每个人在哪个窗口排队或者服务，我们没有必要记录哪些人在哪个窗口——只要记录哪些人在什么时间被服务，在什么时间服务结束即可。当然需要记录还有多少个窗口。我们用一个“事件控制器”——即表示事件的队列，最初每个人达到事件都放入队列里，然后每个人记录一个服务开始的事件，当服务开始的时候我们自然知道它等了多久，累加等待的事件，然后我们也知道他什么时候离开，这样好把可用窗口个数加1。
总的来说 事件包括
(1) 新来一个人
(2) 开始服务一个人
(3) 服务完成一个人
我们分别把这3个时间放到优先队列里，C++ STL有priority_queue，
我更习惯用multiset，虽然实现不一样，但是功能相仿
我们的事件是维度的pair，总的来说是一个开始时间，和一个持续时间。
我是在人离开的时候把持续时间设置为-1了，因为这一维没用了。
总体流程：
（1） 来一个人，放入临时等待队列里。
（2） 出一个人，可用窗口数加1。
（3） 每次如果等待队列里有人就移出一个到窗口。
更新时间now，另外注意8点和17点的限制就好了。
代码很短。
#include <cstdio>
#include <set>
#include <queue>
using namespace std;
multiset<pair<int,int> > all;
queue<pair<int,int> > q;
const int t8 = 8 * 3600;
const int t17 = 17 * 3600;
int main() {
int m,n;
for (scanf("%d%d",&n,&m);n;--n) {
int hh,mm,ss,s;
scanf("%d:%d:%d%d",&hh,&mm,&ss,&s);
int temp = hh * 3600 + mm * 60 + ss;
if (temp <= t17) {
all.insert(make_pair(temp, s * 60));
}
}
int num = 0, total = 0;
for (int now = t8;(!all.empty()) || (!q.empty());) {
if (!all.empty()) {
if (all.begin()->second >= 0) {
q.push(*all.begin());
now = max(now, all.begin()->first);
}
else {
now = all.begin()->first;
++m;
}
all.erase(all.begin());
}
for (;m && (!q.empty()); ++num, --m, q.pop()) {
total += now - q.front().first;
all.insert(make_pair(now + q.front().second, -1));
}
}
printf("%.1lf\n",total / 60. / num);
return 0;
}
原题链接： http://www.patest.cn/contests/pat-a-practise/1017
查看3道真题和解析
