PAT 甲级刷题实录——1014

原题链接

PTA | 程序设计类实验辅助教学平台 千名教师建设，万道高质量题目，百万用户拼题的程序设计实验辅助教学平台 pintia.cn

思路

这题需要用到队列，而且不止一条。首先是每个等待窗口各需要一条，另外在黄线外的等待顾客需要一条。C++ 提供了现成了现成的队列类型，只要引用头文件 queue 即可。

算法基本运行过程是：在输入顾客等待时间时依次填满每条队列，超出队列容量的，即编号大于 N*M+1 的顾客，则 push 进黄线外的等待队列中。当有窗口有顾客处理完毕后，则将该顾客 pop 出队列，同时从黄线外等待队列中 pop 出一个顾客并 push 进该窗口对应的队列中。最后直到黄线外等待队列为空为止。当然，光靠这个基本运行过程去写代码肯定是不行的，因为还需要在算法运行过程中计算每个顾客处理完成的时间，同时还需要判断何时进出队列。这也是本道题最难的两个地方。因为 C++ 没有提供处理时间相关的类型，所以直接用时刻来计算非常麻烦，我们可以转变一种思路，即将时间转换为从 8 点开始经过的分钟数，最后输出结果的时候转换为 HH:MM 形式的时刻即可，这样就大大方便了计算。对于解决两个难点问题，我的思路是：记录每个队列队首元素处理完毕后的时间（从 8 点开始的经过的分钟数）hTime，这个时间也就是黄线外等待队列中的元素能够进入该队列的时间。另外记录每个队列队尾元素处理完毕后的时间（从 8 点开始的经过的分钟数）tTime，这个时间用于计算新进入队列的顾客开始处理的时间以及最终处理完毕的时间。在调度时，每次按队列下标依次找 hTime 最小的队列，将该队列中的队首元素弹出，在队尾插入从黄线外等待队列弹出的元素，同时更新 hTime 和 tTime，并记录新进入队列顾客的开始时间和结束时间。这种方法能够符合题目如果两个队列都有一样多的空位，找编号更小的队列，假设出现多条队列的队首元素同时处理完毕，即多条队列都有空位，因为我们是按下标从小到大找的，只要把判断条件改为小于就能够找到编号最小的队列，而且下一次循环还是能找到编号最小的。对于题目另一个要求，即找最短的队列插入，这个情况实际上只会出现在最初初始化的阶段，初始化之后的运行过程中一旦一条队列有空位马上就会有顾客填入，即所有队列基本都是处于满员状态，最多出现一个空位，不存在多个空位的队列，因此无需考虑长短问题。

另外我在做这题的时候一开始有一个理解有误的地方，我以为只要顾客的结束时间晚于 17:00 那就不能处理了，但实际上是开始时间不能晚于 17:00，如果在 17:00 点前开始了，哪怕最后结束的时间超过了 17:00，也得给他处理完毕。这也是真实工作生活中的情况。

代码

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
struct cInfo
{
	int cNum;	//顾客编号
	int pTime;	//需要处理的时长
	int beginTime, endTime;	//开始处理的时间，结束处理的时间
};
int main()
{
	int N, M, K, Q;
	cin >> N >> M >> K >> Q;
	vector<queue<cInfo> > lines(N+1);
	queue<cInfo> outWait;	//在黄线外等待的顾客
	vector<int> hTime(N + 1, 0);	//队列队首处理完毕后的时间（自8点算起）
	vector<int> tTime(N + 1, 0);	//队列队尾处理完毕后的时间
	vector<cInfo> customers(K+1);	//每位顾客处理完毕后的时间
	for (int i = 0; i < K; i++)
	{
		int pTime, lNum;
		lNum = (i % N) + 1;	//计算队列号
		cin >> pTime;
		cInfo customer;
		customer.cNum = i + 1;
		customer.pTime = pTime;
		if (i < M * N)	//队列还有空位
		{
			if (i < N)
				hTime[lNum] = pTime;	//每个队列添加第一个顾客，确定队首处理完毕后的时间
			lines[lNum].push(customer);
			customer.beginTime = tTime[lNum];	//开始时间为前一个队尾结束的时间
			//customers[i + 1].beginTime = tTime[lNum];	
			tTime[lNum] += pTime;	//更新当前队尾
			customer.endTime = tTime[lNum];
			customers[i + 1] = customer;	//结束时间为更新后的队尾时间
		}
		else	//队列全部已满
		{
			outWait.push(customer);
		}
	}
	while (outWait.size() != 0)	//在黄线外等待的不为空
	{
		int min=hTime[1], num = 1;
		for (int i = 2; i < N + 1; i++)
		{
	
			if (hTime[i] < min)
			{
				min = hTime[i];
				num = i;
			}
		}
		lines[num].pop();
		cInfo c = outWait.front();
		outWait.pop();
		lines[num].push(c);
		hTime[num] += lines[num].front().pTime;
		customers[c.cNum].beginTime = tTime[num];
		tTime[num] += c.pTime;
		customers[c.cNum].endTime = tTime[num];
	}
	for (int i = 0; i < Q; i++)
	{
		int cNum;
		cin >> cNum;
		if (customers[cNum].beginTime >= 540)
			cout << "Sorry" << endl;
		else
		{
			int hour, minute;
			hour = 8 + customers[cNum].endTime / 60;
			minute = customers[cNum].endTime % 60;
			if (hour < 10)
				cout << '0' << hour << ':';
			else
				cout << hour << ':';
			if (minute < 10)
				cout << '0' << minute << endl;
			else
				cout << minute << endl;
		}
	}
	return 0;
}
​