7-48 银行排队问题之单窗口“夹塞”版 (30 分)

#include<iostream>
#include<cstring>
#include<unordered_map>
#include<vector>
#include<algorithm>
 
using namespace std;
 
struct customer {	//定义顾客结构体 
	char name[4];
	int arriveTime, processTime;
};
 
int N, M;
unordered_map<string, int> friendMap, customerId;	//friendMap存储每个人所属的朋友圈编号，customerId存储每个人名的到达顺序 
bool visited[10000];	//visited[]数组标记第i个到达的人是否已经被处理过 
vector<string> friends[100], result;	//friends[i]存储朋友圈编号为i的朋友名，result存储结果 
 
bool cmp(string s1, string s2);
 
int main() {
	scanf("%d %d", &N, &M);
	fill(visited, visited + N, false); 
	for(int i = 0; i < M; i++) {
		int L;
		scanf("%d", &L);
		for(int j = 0; j < L; j++) {
			char name[4];
			scanf("%s", name);
			friendMap[name] = i;
			friends[i].push_back(name);
		}
	}
	customer customers[N];
	for(int i = 0; i < N; i++) {
		char name[4];
		scanf("%s %d %d", name, &customers[i].arriveTime, &customers[i].processTime);
		if(customers[i].processTime > 60) {	//如果单次处理时间超过60，当作60处理 
			customers[i].processTime = 60;
		}
		strcpy(customers[i].name, name);
		customerId[name] = i;
	}
	int totalTime = 0;	//总等待时间 
	int window = customers[0].arriveTime;	//一开始的窗口时间应该设置为最先到达的顾客的到达时间 
	for(int i = 0; i < N; i++) {
		if(visited[i]) {	//如果该顾客已经被处理过了，则跳过本次循环 
			continue;
		}
		if(friendMap.find(customers[i].name) == friendMap.end()) {	//如果该顾客不属于任何一个朋友圈 
			if(window > customers[i].arriveTime) {	//如果窗口时间大于顾客的到达时间 
				totalTime += window - customers[i].arriveTime;	//总等待时间增加 
				window += customers[i].processTime;	//窗口时间加上该顾客的处理时间 
			}else{
				window = customers[i].arriveTime + customers[i].processTime;	//窗口时间更新为顾客的到达时间加上该顾客的处理时间 
			}
			visited[i] = true;	
			result.push_back(customers[i].name);
			continue;	//跳过本次循环 
		}
		int friendID = friendMap[customers[i].name];
		sort(friends[friendID].begin(), friends[friendID].end(), cmp);	//对该顾客所属朋友圈的朋友按到达顺序进行排序 
		for(int j = 0; j < friends[friendID].size(); j++) {
			int id = customerId[friends[friendID][j]];
			if(j > 0 && customers[id].arriveTime > window){	//如果下一个朋友的在window的空闲时间之前没有到达，则无法插队 
				break;
			}
			if(visited[id]){
				continue;
			}
			if(window > customers[id].arriveTime) {
				totalTime += window - customers[id].arriveTime;
				window += customers[id].processTime;
			} else {
				window = customers[id].arriveTime + customers[id].processTime;
			}
			visited[id] = true;
			result.push_back(friends[friendID][j]);
		}
	}
	for(int i = 0; i < result.size(); i++) {	//输出结果 
		printf("%s\n", result[i].c_str());
	}
	printf("%.1f\n", totalTime * 1.0 / N);
	return 0;
}
 
bool cmp(string s1, string s2) {
	return customerId[s1] < customerId[s2];
}