|
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:
- The space inside the yellow line in front of each window is enough to contain a line with?M?customers. Hence when all the?N?lines are full, all the customers after (and including) the?(NM+1)st one will have to wait in a line behind the yellow line.
- Each customer will choose the shortest line to wait in when crossing the yellow line. If there are two or more lines with the same length, the customer will always choose the window with the smallest number.
- Customeri??will take?Ti??minutes to have his/her transaction processed.
- The first?N?customers are assumed to be served at 8:00am.
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 customers 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,?customer1??is served at?window1??while?customer2??is served at?window2?.?Customer3??will wait in front of?window1??and?customer4??will wait in front of?window2?.?Customer5??will wait behind the yellow line.
At 08:01,?customer1??is done and?customer5??enters the line in front of?window1??since that line seems shorter now.?Customer2??will leave at 08:02,?customer4??at 08:06,?customer3??at 08:07, and finally?customer5??at 08:10.
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 Specification:
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 5
1 2 6 4 3 534 2
3 4 5 6 7
Sample Output:
08:07
08:06
08:10
17:00
Sorry
这题我没有采用队列容器的方式，主要是利用数学关系，但采用了队列的思想。
思路是：首先想想前N*M个数肯定是已经排好队了，前N个客户的完成时间必定是其办理业务的时间，而后面N*(M-1)个客户的完成时间就是其前一个客户的完成时间加上自己办理业务的时间，这段代码是：
if(i<N) time[i] = process[i];
else if(i>=N && i<N*M) time[i] = process[i] + time[i-N];? ?
而后面的>=（N*M+1）的客户应该是看见哪个队列先腾出一个人来了就往哪个地方去，也就是说先办理完业务的那一个窗口，那我们就比较一下窗口前那些正在办理业务的客户的完成时间，谁最小就去哪个窗口，而完成时间就是这个队列的最后一个人的完成时间加上自己的办理业务的时间。
整理成代码的思路就是：客户x的前N*M个人中的前N个完成时间的大小比较（比较拗口，自己画画图就明白了）
?? ?int length = N*M, i;
?? ?int min = x-length;
?? ?for(i=x-length;i<x-length+N;i++){
?? ??? ?if(time[i]<time[min]) min = i;
?? ?}
?? ?return min;? ? ? ?
min是正在窗口前办理业务的人的下标，想要知道客户x的完成时间，我们还得知道这个队列最后一个人的完成时间，也就是min+N*(M-1)的客户的完成时间（自己再画画图）。
最后，注意一个大坑，我们上述思路计算的是完成时间，但决定能不能办理业务的不是完成时间，而是开始时间，因为如果你从16:00办理业务，需要2小时，总不能在17:00的时候把你赶走吧，所以在判断能否办理业务的时候，我们需要的是开始时间，那就用我们的完成时间-办理业务的时间就好了。
好的，思路清晰了，上代码：
?
//1014 Waiting in Line (30 分)
#include<stdio.h>
int FindMinN(int x, int time[]);
int N, M, K, Q;
int main()
{
?? ?scanf("%d%d%d%d", &N, &M, &K, &Q);
?? ?int i=0, process[K], time[K];
?? ?for(i=0;i<K;i++){
?? ??? ?scanf("%d", &process[i]);
?? ?}
?? ?
?? ?for(i=0;i<K;i++){
?? ??? ?if(i<N) time[i] = process[i];
?? ??? ?else if(i>=N && i<N*M) time[i] = process[i] + time[i-N];
?? ??? ?else{
?? ??? ??? ?int min = FindMinN(i, time);
?? ??? ??? ?time[i] = time[min+N*(M-1)] + process[i];
?? ??? ?}
?? ?}
?? ?
?? ?for(i=0;i<Q;i++){
?? ??? ?int number;
?? ??? ?scanf("%d", &number);
?? ??? ?number = number - 1;
?? ??? ?if((time[number]-process[number])<540){
?? ??? ??? ?int hour = 8 + time[number]/60;
?? ??? ??? ?int minute = time[number]%60;
?? ??? ??? ?printf("%02d:%02d", hour, minute);
?? ??? ?}?
?? ??? ?else printf("Sorry");
?? ??? ?if(i!=Q-1) printf("\n");
?? ?}
?? ?return 0;
}
int FindMinN(int x, int time[])
{
?? ?int length = N*M, i;
?? ?int min = x-length;
?? ?for(i=x-length;i<x-length+N;i++){
?? ??? ?if(time[i]<time[min]) min = i;
?? ?}
?? ?return min;
}
|