PAT A1017 Queueing at Bank (25)

PTA跳转：原题链接

这道题大意是：输入客户数量和窗口数量，然后输入每个客户的到达时间和服务时间。如果有空闲窗口，客户可直接办理业务；如果没有窗口，则需等待至其中一个窗口完成对前一个客户的服务才能进行业务办理。如果客户到达时间早于开始营业时间（8点），需等待至8点；如果到达时间晚于截止营业时间（17点），则不接受业务办理。最后输出客户的平均等待时间。

我认为这道题难点在于：如何找到最快完成服务的窗口。其实，用STL中的优先队列可以很好解决这一问题。使用优先队列，每次入队和出队时，都会自动按照自定义的规则来进行排序。要注意的是，每一次入队后要把队头出队，保证队列元素数量不变。

还有一个卡了比较长时间的点：用户到达，如果有空闲窗口，入队元素是(arrive+serve)；如果没有空闲窗口，入队元素是(q.top()+serve)，这两种情况是不一样的。（其中q.top()是最先成为空闲窗口的时间）

代码如下：

#include <iostream>
#include <algorithm>
#include <queue>
#include <iomanip>
using namespace std;

#define MAX 10000

struct Customer{
	int arrive, serve;
}cus[MAX];

bool cmp(Customer a, Customer b){
	return a.arrive < b.arrive;
}

int main(){
	int m, n;	//m,n分别表示客户数量和窗口数量
	int HH, MM, SS, arr, ser, avg = 0;	//HH,MM,SS分别表示时分秒，arr,ser分别为到达时间和服务时间 
	cin >> m >> n; 
	
	for(int i = 0; i < m; i++){
		scanf("%d:%d:%d", &HH, &MM, &SS);
		cin >> ser;
		arr = HH * 3600 + MM * 60 + SS;
		if(arr > 61200){	//61200=3600*17，超过17点 
			i--;
			m--;	//可以保证循环次数不变
			continue;
		}
		cus[i].arrive = arr;
		cus[i].serve = ser * 60;
	} 
	
	sort(cus, cus + m, cmp);	//排序
	
	priority_queue<int, vector<int>, greater<int> > q;
	for(int i = 0; i < n; i++){
		q.push(28800);	//28800=3600*8，初始化为8点 
	}
	
	for(int i = 0; i < m; i++){
		int top = q.top();
		if(top <= cus[i].arrive){	//有空闲窗口 
			q.push(cus[i].arrive + cus[i].serve);
			q.pop();
		}
		else if(top > cus[i].arrive){	//无空闲窗口，需要等待 
			avg += top - cus[i].arrive;
			q.push(top + cus[i].serve);
			q.pop();
		}
	}
	cout << fixed << setprecision(1) << (float)avg / m / 60.0;
	return 0;
}
           

氷鸢鸢鸢

2020.3.27