PAT 甲级 1014 Waiting in Line （30 分)

今天这两道模拟题没折磨死我。
Note：
1、思路
这题思路还挺难想的。因为线外的人到哪个窗口办理业务是未知的，所以只能把黄线内先填满，然后用模拟（走一个进一个）的方式来计算每个人的开始时间。
2、数据结构
一开始想的是只用结构体和数组，但后来发现这样在模拟的时候没法获取窗口第二个人的信息。所以还是选择了queue。结构体根据题意来确定，因为窗口和顾客都含有多种数据，所以选择两个结构体。
窗口结构体
首先要有一个队列，然后因为每个窗口限制人数，所以要有一个长度（queue自带），又因为要寻找最早完成的窗口，所以我们需要知道每个窗口当前顾客的结束时间，可以单独存储也可以利用queue.front()来获取。因为还要知道一个人是否会被拒绝服务，所以顾客的结构体里会有一个start，而start值的确定就需要窗口队列的最后一个人的完成时间，我们也可以用last来单独存储。
顾客结构体
首先要知道一个人是否可能会被拒绝，所以有一个start来表示开始受理的时间，finish表示结束时间，process表示处理时间。（finish可能比较多余，没有细想）

需要的数据结构都知道了以后这题其实就没有那么难了，然后就是模拟过程的时候细心一点就好了。
3、注意
注意样例给的那个，因为窗口二比窗口一更早少一个人，所以7号顾客加入了窗口二的队列，就算他在排队过程中窗口一没人了他也不能换队伍。
push进行的是复制操作，push一个结构体到queue中，原来结构体发生改变，queue的结构体还是原值。所以在push的时候要注意结构体有没有更新完。

Code：

#include<iostream>
#include<algorithm>
#include<queue>

using namespace std;

struct customer {
	int start;//预计开始受理的时间
	int finish;//预计的结束时间
	int process;
}cus[1002];

struct window {
	int finish;//第一个人的结束时间
	int last;//最后一个人的结束时间
	queue<int> q;//存储排队的人的序号
}win[21];

int main() {
	int n, m, k, q;
	cin >> n >> m >> k >> q;
	for (int i = 1; i <= k; i++)
	{
		cin >> cus[i].process;
	}

	int close = (17 - 8) * 60;//关门时间，以min为单位

	/*计算每个人的完成时间*/
	int first = 1;//线外的第一个人的序号
	for (first = 1; first <= m * n&&first <= k;)
	{//填满黄线内
		for (int i = 1; i <= n; i++)
		{//遍历每个窗口
			if (first <= n * m && first <= k) {
				if (win[i].q.size() < m) {
					cus[first].start = win[i].last;
					cus[first].finish = cus[first].start + cus[first].process;
					if (win[i].q.size() == 0) win[i].finish = cus[first].process;
					win[i].q.push(first);
					win[i].last = cus[first].finish;
					first++;
				}
			}
			else
				break;
		}
	}

	/*模拟*/
	for (int i = first; i <= k; i++)
	{
		/*找最先完成的窗口*/
		int min = win[1].finish;
		int min_win = 1;
		for (int j = 1; j <= n; j++)
		{
			if (win[j].finish < min) {
				min = win[j].finish;
				min_win = j;
			}
		}
		win[min_win].q.pop();//最早完成的窗口出队
		customer temp = cus[win[min_win].q.front()];//刚出队那个人的后面一个人
		//更新窗口信息，并让一个人入队
		win[min_win].finish = temp.finish;
		cus[i].start = win[min_win].last;//更新开始时间为该窗口最后一个人的结束时间
		cus[i].finish = cus[i].start + cus[i].process;
		win[min_win].q.push(i);
		win[min_win].last = cus[i].finish;
	}

	/*查询*/
	for (int i = 0; i < q; i++)
	{
		int seq;
		cin >> seq;
		if (cus[seq].start < 9 * 60) {
			printf("%02d:%02d\n", cus[seq].finish / 60 + 8, cus[seq].finish % 60);
		}
		else {
			printf("Sorry\n");
		}
	}
	return 0;
}