1014. Waiting in Line (30)

Suppose a bank has N windows open for service. There is a yellow line in front of the windows which devides the waiting area into two parts. The rules for the customers to wait in line are:

Now given the processing time of each customer, you are supposed to tell the exact time at which a customer has his/her business done.

For example, suppose that a bank has 2 windows and each window may have 2 custmers waiting inside the yellow line. There are 5 customers waiting with transactions taking 1, 2, 6, 4 and 3 minutes, respectively. At 08:00 in the morning, customer₁ is served at window₁ while customer₂ is served at window₂. Customer₃ will wait in front of window₁ and customer₄ will wait in front of window₂. Customer₅ will wait behind the yellow line.

At 08:01, customer₁ is done and customer₅ enters the line in front of window₁ since that line seems shorter now. Customer₂ will leave at 08:02, customer₄ at 08:06, customer₃ at 08:07, and finally customer₅ at 08:10.

Input

Each input file contains one test case. Each case starts with a line containing 4 positive integers: N (<=20, number of windows), M (<=10, the maximum capacity of each line inside the yellow line), K (<=1000, number of customers), and Q (<=1000, number of customer queries).

The next line contains K positive integers, which are the processing time of the K customers.

The last line contains Q positive integers, which represent the customers who are asking about the time they can have their transactions done. The customers are numbered from 1 to K.

Output

For each of the Q customers, print in one line the time at which his/her transaction is finished, in the format HH:MM where HH is in [08, 17] and MM is in [00, 59]. Note that since the bank is closed everyday after 17:00, for those customers who cannot be served before 17:00, you must output "Sorry" instead.

2 2 7 51 2 6 4 3 534 23 4 5 6 7Sample Output
08:0708:0608:1017:00Sorry
#include<cstdio>#include<queue>#include<algorithm>using namespace std;const int maxn = 22;const int maxk = 1000 + 10;int N, M, K, Q;int nowTime = 0;int CloseTime = (17 - 8) * 60;struct customer{	int id;	int processtime;	int donetime;	customer():donetime(-1){}}customers[maxk];queue<customer> line[maxn],behindQueue;int lastTime[maxn] = { 0 };int main(){	scanf("%d%d%d%d", &N, &M, &K, &Q);//注意N、M的意义	int capacity = N*M;	for (int i = 1; i <= K; i++)	{		scanf("%d", &customers[i].processtime);		customers[i].id = i;		if (i <= capacity)		{			line[(i - 1) % N + 1].push(customers[i]);		}		else			behindQueue.push(customers[i]);//排队	}	int countC = K;	while (nowTime < CloseTime&&countC)//模拟时间流动，每分钟检查一次有不有完成的	{		nowTime++;		for (int i = 1; i <= N; i++)		{			if (!line[i].empty())			{				int donetime = line[i].front().processtime + lastTime[i];				int id = line[i].front().id;				if ((donetime>CloseTime||donetime == nowTime)&&lastTime[i]<nowTime)				{					customers[id].donetime = donetime;					lastTime[i] = donetime;					line[i].pop();					countC--;					if (behindQueue.size())					{						line[i].push(behindQueue.front());						behindQueue.pop();					}				}				else if (lastTime[i] >= nowTime)				{					line[i].pop();					countC--;					if (behindQueue.size())					{						line[i].push(behindQueue.front());						behindQueue.pop();					}				}			}		}	}	int query;	for (int i = 0; i < Q; i++)	{		scanf("%d", &query);		if (customers[query].donetime != -1)			printf("%02d:%02d/n", 8 + customers[query].donetime / 60, customers[query].donetime % 60);		else			printf("Sorry/n");	}}