1017. Queueing at Bank 解析

注意：后面来的顾客是有可能不用排队的。 比如11：00顾客没有了13：00来人了是不用排队的。

在选取窗口的时候方法和之前那个1014的选择方法不同。注意对比。

#include <iostream>#include <vector>#include <algorithm>#include <string>#include <map>#include <queue>using namespace std;struct Node{	string time;	int p;};int char2int(char c) {	return int(c) - int('0');}int str2int(string s) {	return (char2int(s[0]) * 10 + char2int(s[1])) * 3600 + (char2int(s[3]) * 10 + char2int(s[4])) * 60 + (char2int(s[6]) * 10 + char2int(s[7]));}bool cmp(Node N1, Node N2) {	if (str2int(N1.time) < str2int(N2.time))		return true;	return false;}int FindWin(queue <Node> * window, int K) { //找最优窗口	int minI = 0;	int minSize = window[0].size();	for (int i = 0; i < K; i++) {		if (minSize > window[i].size()) {			minSize = window[i].size();			minI = i;		}	}	return minI;}int DeWin(queue <Node> * window, int K) { //窗口出队	int minI = 0;	int minTime = window[0].front().p;	for (int i = 0; i < K; i++) {		if (minTime > window[i].front().p) {			minTime = window[i].front().p;			minI = i;		}	}	for (int i = 0; i < K; i++) { //出队		if (minTime == window[i].front().p)			window[i].pop();	}	return minI;}int main( ){	int N, K;	cin >> N >> K;			vector <Node> tempNV;	Node tempN;		int TrueNum = 0;	for (int i = 0; i < N; i++) {		cin >> tempN.time >> tempN.p;		if (str2int(tempN.time) <= 17 * 3600) {			TrueNum++;			if (tempN.p > 60)				tempN.p = 60;			tempNV.push_back(tempN);		}			}	N = TrueNum;	Node * List = new Node[N];	for (int i = 0; i < N; i++) {		List[i] = tempNV[i];	}		sort(List, List + N, cmp);	int * time = new int[N];//服务时间	int * winTime = new int[K];//窗口计时	int startTime = 8 * 3600; //开始时间	int endTime = 17 * 3600 ; //结束时间	int Num = 0;	for (int i = 0; i < K; i++) {		winTime[i] = startTime;	}				int SumWait = 0; //等待总时间	int tempWin = 0; //选择窗口		queue <Node> * window = new queue<Node>[K];	for (int i = 0; i < N; i++) {		time[i] = str2int(List[i].time); //到达时间		//tempWin = FindWin(window, K);		//if (window[tempWin].size() < 1) {		//	window[tempWin].push(List[i]);		//}		//else {		//	tempWin = DeWin(window, K);		//	window[tempWin].push(List[i]);		//}		int Min = winTime[0];		tempWin = 0;		for (int i = 0; i < K; i++) {			//cout << winTime[i] << " ";			if (Min > winTime[i]) {				Min = winTime[i];				tempWin = i;			}		}		//cout << endl;		//cout << tempWin << endl;						if (winTime[tempWin] <= time[i]) {//窗口上次服务结束时间小于到达时间 无需等待			winTime[tempWin] = time[i] + List[i].p * 60;		}		else{ //需要等待			SumWait += (winTime[tempWin] - time[i]);			winTime[tempWin] += List[i].p * 60;		}		//cout << "win = " << tempWin << endl;		//cout << List[i].time << " " << List[i].p << endl;		//cout << "WIN: " << winTime[tempWin] << " Arrive：" << time[i] << endl;		//cout << SumWait << endl;		//cout << endl;	}//	cout << SumWait << endl;	if (N <= 0) cout << "0.0" << endl;	else {		float average = SumWait / 60.0 / TrueNum;		PRintf("%.1f", average);		cout << endl;	}	return 0;}