1014 Waiting in Line (30分)
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
思路
这道题是一个银行队列的模拟，具体处理比较复杂，要想不超时，思路必须要转换，重点在于从8点开始枚举每一分钟，以及排第1的出队之后要更新排第2的人的已等待时间cost。
有个题意理解有偏差的地方：
只要在17:00之前进入窗口进行业务办理，但还未办理完成的，不管多久，都会到办理完成为止
例：一个人16:49分进入1号窗口办理业务，要办理120分钟，则他的完成时间为18:49
一开始53行的n我给写成了m，导致有三个测试点超时，我说这思路不可能超时啊，搞得我还以为思路错了，找了很久才发现是这里的问题，以后一定要仔细，写代码不能着急、浮躁。
一开始出现了越界错误，也让我找了很久很久越界的地方，以后使用stl容器的成员方法的时候，一定要记得判空！
具体思路见代码，注释写的很详细：
1 #include <iostream>
2 #include <stdio.h>
3 #include <deque>
4
5 using namespace std;
6
7 int n, m, k, qs;
8 struct Customer
9 {
10 int id;
11 int start_time;
12 int cost; //耗时
13 }c[1100];
14
15 int f[1100]; //完成时间
16
17 deque<Customer> Q[32]; // 窗口Q[i]的队伍
18
19 int main()
20 {
21 // qs表示查询人数queries
22 scanf("%d%d%d%d", &n, &m, &k, &qs);
23 for(int i = 1; i <= k; ++i)
24 {
25 c[i].id = i;
26 scanf("%d", &c[i].cost);
27 }
28
29 // 初始化窗口队伍, 编号从1开始
30 for(int i = 1; i <= m*n && i <= k; ++i)
31 {
32 if(i % n == 0)
33 Q[n].push_back(c[i]);
34 else
35 Q[i%n].push_back(c[i]);
36 }
37
38 // 初始化每个队伍的队首人的开始时间
39 for(int i = 1; i <= n; ++i)
40 {
41 if(!Q[i].empty())
42 Q[i][0].start_time = 0;
43 }
44
45 int w = m*n+1; //w表示此时排在等待队列的第一个人的序号
46 int finishedCustomerNum = 0; // 已经完成的顾客
47
48 // 从08:00开始遍历，540分钟就是17:00
49 for(int i = 1; finishedCustomerNum < k; ++i)
50 {
51 // 遍历所有队伍，考察其队首
52 for(int j = 1; j <= n; ++j)
53 {
54 if(!Q[j].empty())
55 {
56 // 开始时间已经到了17:00，则后面的人全都无法继续办理
57 if(Q[j][0].start_time >= 540)
58 {
59 while(!Q[j].empty())
60 {
61 f[Q[j].front().id] = -1;
62 Q[j].pop_front();
63 finishedCustomerNum++;
64 }
65 // 并且把剩余的等待的人全部清除
66 for(; w <= k; ++w)
67 {
68 f[w] = -1;
69 finishedCustomerNum++;
70 }
71 continue;
72 }
73 if(i == Q[j][0].cost)
74 {
75 // 记录队首元素离队时间
76 f[Q[j][0].id] = i;
77 // 更新排在第二的人的开始时间
78 Q[j][1].start_time = i;
79 // 排在第二的人耗时必须加上刚刚离队的那个人
80 Q[j][1].cost += Q[j][0].cost;
81 // 排在队首的人离队
82 Q[j].pop_front();
83 // 已经完成的人数+1
84 finishedCustomerNum++;
85
86 // 当前排在第一个等待队列的人入队
87 if(w <= k)
88 {
89 Q[j].push_back(c[w]);
90 w++;
91 }
92 }
93 }
94
95 }
96 }
97
98
99 for(int x = 1; x <= qs; ++x)
100 {
101 int qc; //待查询的顾客，query customer
102 scanf("%d", &qc);
103 if(f[qc] == -1)
104 {
105 if(x == qs)
106 printf("Sorry");
107 else
108 printf("Sorry\n");
109 continue;
110 }
111 int hour = f[qc] / 60;
112 int minute = f[qc] % 60;
113 // 从08:00开始，所以要+8
114 hour = hour + 8;
115 if(hour < 10)
116 printf("0");
117 printf("%d", hour);
118 printf(":");
119 if(minute < 10)
120 printf("0");
121 printf("%d", minute);
122 if(x < qs)
123 printf("\n");
124 }
125
126 return 0;
127 }