Jobdu -1326-Waiting in Line-模拟题 | Acm之家

九度-1326-Waiting in Line-模拟题 | Acm之家

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.
• Customer[i] will take T[i] 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 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.

输入：

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.

输出：

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

样例输出：

08:07  08:06  08:10  17:00  Sorry

题目大意：
有K个客户去银行办理业务，黄线内可以排队M个人。黄线外的人会优先选择人数少的队去排。 每个人花费的时间是不一样的。问每个人业务结束的时间。稍微有些繁琐的模拟。即使是17点之前开始办业务，17点之后仍然没有办完就是sorry。




PAT 1014. Waiting in Line

1. typedef struct customer  
2. {  
3.     int begin;  
4.     int end;  
5.     int trans;  
6. }Customer;  
7.   
8. Customer c[MAX];  
9.   
10. int main(int argc,char *argv[])  
11. {  
12.     int n,m,k,q;  
13.     int i,j;  
14.     queue<int> windows[20];  
15.     int now,shut_time;  
16.     int count,to_finish;  
17.     scanf("%d%d%d%d",&n,&m,&k,&q);  
18.     for(i=1;i<=k;i++)  
19.     {  
20.         scanf("%d",&c[i].trans);  
21.         c[i].begin=-1;  
22.         c[i].end=-1;  
23.     }  
24.     now=0;  
25.     shut_time=(17-8)*60;  
26.     count=1;  
27.     for(i=0;i<n&&count<=k;i++)//向N个窗口压入一个顾客，开始时间为零  
28.     {                         //结束时间为交易时间  
29.         windows[i].push(count);  
30.         c[count].begin=0;  
31.         c[count].end=c[count].trans;  
32.         count++;  
33.     }  
34.     for(i=0;i<m-1&&count<=k;i++)//向N个窗口压入分别M-1个顾客，开始时间  
35.         for(j=0;j<n&&count<=k;j++)//是上一个结束时间，结束时间是开始时间  
36.         {                         //加上交易时间  
37.             c[count].begin=c[windows[j].back()].end;  
38.             c[count].end=c[count].begin+c[count].trans;  
39.             windows[j].push(count);  
40.             count++;  
41.         }  
42.     while(count<=k&&now<shut_time)//将第N*M+1以及之后  
43.     {                   //顾客插入最先离开顾客的窗口  
44.         to_finish=0;//其为即将完成交易的顾客的窗口编号  
45.         for(i=1;i<n;i++)  
46.          if(c[windows[i].front()].end<c[windows[to_finish].front()].end)  
47.              to_finish=i;//找到最先完成的窗口号  
48.         now=c[windows[to_finish].front()].end;  
49.         windows[to_finish].pop();  
50.         c[count].begin=c[windows[to_finish].back()].end;  
51.         c[count].end=c[count].begin+c[count].trans;  
52.         windows[to_finish].push(count);  
53.         count++;  
54.     }  
55.     for(i=0;i<q;i++)  
56.     {  
57.         int query;  
58.         scanf("%d",&query);  
59.         if(c[query].end==-1||c[query].begin>=shut_time)//从某个顾客开始  
60.             printf("Sorry\n");                     //还没服务就要关门了  
61.         else  
62.             printf("%.2d:%.2d\n",c[query].end/60+8,c[query].end%60);  
63.     }  
64.   
65.     return 0;  
66. }  

http://www.acmerblog.com/jiudu-1326-waiting-in-line-3761.html
http://blog.csdn.net/u013027996/article/details/17475331

1. int main(){  
2.     while(scanf("%d%d%d%d",&n,&m,&k,&q) != EOF){  
3.         for(i = 1; i < k+1; i++){  
4.             scanf("%d",&taskArr[i]);  
5.         }  
6.         for(i = 0; i < n; i++){  
7.             while(!qu[i].empty()){  
8.                 qu[i].pop();  
9.             }  
10.         }  
11.         memset(allTime,0,sizeof(allTime));  
12.         int count = 0;  
13.         for(i = 0; i < m; i++){  
14.             for(j = 0; j < n; j++){  
15.                 count++;  
16.                 if(count > k){  
17.                     break;  
18.                 }  
19.                 allTime[count] = taskArr[count];  
20.                 if(!qu[j].empty()){  
21.                     allTime[count] += allTime[qu[j].back()];  
22.                 }  
23.                 qu[j].push(count);  
24.             }  
25.             if(count > k){  
26.                 break;  
27.             }  
28.         }           
29.         while(count < k){  
30.             count++;  
31.             int minTime = allTime[qu[0].front()];  
32.             int groupId = 0;  
33.             for(i = 1; i < n; i++){  
34.                 int tempTime = allTime[qu[i].front()];  
35.                 if(tempTime < minTime){  
36.                     minTime = tempTime;  
37.                     groupId = i;  
38.                 }     
39.             }  
40.             allTime[count] = taskArr[count];  
41.             if(!qu[groupId].empty()){  
42.                 allTime[count] += allTime[qu[groupId].back()];  
43.             }  
44.             qu[groupId].pop();  
45.             qu[groupId].push(count);  
46.         }  
47.         int rank;  
48.         for(i = 0; i < q; i ++){  
49.             scanf("%d",&rank);  
50.             if(allTime[rank] > 540){  
51.                 printf("Sorry\n");  
52.             }else{  
53.                 printf("%02d:%02d\n",8 + allTime[rank]/60,allTime[rank]%60);  
54.             }  
55.         }  
56.     }  
57.     return 0;  
58. }   

http://noalgo.info/697.html
http://www.hijeffrey.com/pat-advanced-1014-waiting-in-line.html

1. typedef struct Customer{  
2.     //开始服务的时间,为了后续判断是否在 17：00前进行服务   
3.     int startTime;   
4.     int endTime;  
5.     //服务时间   
6.     int processTime;   
7. }Customer;   
8. typedef struct Window{  
9.     int head;  
10.     int tail;  
11.     //最大在黄线内就10人   
12.     int winQueue[WINWAIT];  
13.     //窗口当前服务结束时间   
14.     int endTime;  
15. }Win;   
16. int main(int argc, char *argv[]) {  
17. //  freopen("1.txt","r",stdin);  
18.     //定义及初始化   
19.     Customer cus[1010];  
20.     Win win[25];   
21.         int N,M,K,Q;  
22.     int i,j;  
23.     for( i = 0 ; i < 1010 ; i++ ){  
24.         cus[i].startTime = 0;  
25.         cus[i].endTime = 0;  
26.         cus[i].processTime = 0;  
27.     }  
28.     for( i = 0 ; i < 25 ; i++ ){  
29.         win[i].endTime = 0;  
30.         win[i].head = 0;  
31.         win[i].tail = 0;  
32.     }  
33.     //数据录入  
34.     scanf("%d%d%d%d",&N,&M,&K,&Q);  
35.     for( i = 1 ; i <= K ; i++) {  
36.         scanf("%d",&cus[i].processTime);  
37.     }  
38.     //进行处理  
39.     i = 1 ;   
40.     //用 i 表示 排在黄线内的客户 ,   
41.     //用 j 表示 当前的窗口号，从小到大为黄线内的客户服务，注意后面 j 赋值的意义   
42.     for( j = 0 ; i <= N * M && i <= K ; i++, j=(j+1)%N ){  
43.         //当前客户服务的开始时间就是窗口为前一个客户服务的结束时间   
44.         cus[i].startTime = win[j].endTime ;  
45.         //客户服务结束   
46.         cus[i].endTime = win[j].endTime + cus[i].processTime;  
47.         //更新当前窗口服务结束时间以便为下一位服务  
48.         win[j].endTime += cus[i].processTime;  
49.         //对窗口进行入队操作  
50.         win[j].winQueue[win[j].tail] = i ;   
51.         win[j].tail =([win[j].tail +1)%WINWAIT ; //这里也需要取模,不然会越界!  
52.         //坑,一开始考虑是不需要的,如果取模不就覆盖第一个排队的,后来朋友说只是下标到第一个没有覆盖  
53.         //想想也对，也不知道一开始怎么想的。  
54.     }   
55.     //黄线内满之后还有客户需要服务 再计算他们的服务时间   
56.     //从黄线前找出服务时间最早结束的窗口，出队，再把一个黄线后的客户入队   
57.     int minTime;  
58.     int cIndex;  
59.     int pos;  
60.     for( ; i <= K ; i++){  
61.         minTime = INF;  
62.         for( j = 0 ; j < N ; j++ ){  
63.             //排在窗口 j 的第一个客户   
64.             cIndex = win[j].winQueue[ win[j].head ];  
65.             if( cus[cIndex].endTime < minTime ){  
66.                 minTime = cus[cIndex].endTime;  
67.                 pos = j;  
68.             }  
69.         }  
70.         //找到最早结束的一个窗口  
71.         cus[i].startTime = win[pos].endTime ;  
72.         //客户服务结束   
73.         cus[i].endTime = win[pos].endTime + cus[i].processTime;  
74.         //更新当前窗口服务结束时间以便为下一位服务  
75.         win[pos].endTime += cus[i].processTime;  
76.         //对窗口进行入队操作  
77.         win[pos].head = (win[pos].head+1)%WINWAIT;   
78.         win[pos].winQueue[win[pos].tail] = i ;   
79.         win[pos].tail = (win[pos].tail+1)%WINWAIT;  
80.     }     
81.     //查询输出  
82.     int hour,minutes;  
83.     while(Q--){  
84.         scanf("%d",&j);  
85.         if( cus[j].startTime + 8*60 >= 17*60 ){  
86.               printf("Sorry\n");    
87.         }else{  
88.              hour = (cus[j].endTime + 8*60) / 60;  
89.              minutes = (cus[j].endTime + 8*60) % 60;  
90.             printf("%02d:%02d\n",hour,minutes);    
91.         }  
92.     }   
93.     return 0;  
94. } 

Read full article from 九度-1326-Waiting in Line-模拟题 | Acm之家