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