题意
在一家银行里有n个服务窗口，每个窗口最多有m个人排队。当窗口都满人时，客户就必须在线外等候，当有人完成服务时，便可上去排队。
客户选择服务窗口的标准为：首先选择排队人数少的窗口，在人数相同的情况下，优先选择最小的窗口号。
现在给出k个客户所需的服务时间，以及q个询问，输出每个询问的客户完成的时间点。
思路
首先我们会想到的是比较每个窗口的第一个客户的服务时间，所需时间短的就会最快完成，此时在线外等候的客户就可以在该窗口排上队。
所以可以用n个队列来维护每个窗口的排队情况。
这里需要注意的是，假设我们第i个窗口有一个客户完成了服务，其服务时间为t，接下来再比较每个窗口第一个客户的服务时间时，除第i个窗口之外，其余窗口第一个客户的服务时间都要减去t，因为每个窗口都是同时进行的。
还有一点需要注意的是，在17:00之前被服务即可，不是指完成时间得在17:00之前。
代码
1 #include<iostream>
2 #include<cstdio>
3 #include<queue>
4 #include<vector>
5 using namespace std;
6 typedef pair<int, int> pii;
7
8 int n, m, k, q;
9
10 queue<pii> Q[25]; //维护窗口排队情况
11 vector<int> line; //线外等候客户
12 int mt[25]; //减去时间
13 int wt[25]; //每个窗口的时间线
14 int res[1005]; //每个客户的完成时间
15 int pt[1005]; //客户服务时间
16
17 int main(){
18 //freopen("in.txt", "r", stdin);
19 scanf("%d%d%d%d", &n, &m, &k, &q);
20 int w = 1;
21 for(int i=1; i<=k; i++){
22 scanf("%d", &pt[i]);
23 if(i > n*m) line.push_back(pt[i]);
24 else{
25 if(w > n) w = 1;
26 Q[w].push(make_pair(i, pt[i]));
27 w++;
28 }
29 }
30
31 int tot = line.size();
32 int cnt = 1;
33
34 for(int i=1; i<=k; i++){
35 int min_time = 0x3f3f3f3f, pos;
36 for(int w=1; w<=n; w++){
37 if(Q[w].empty()) continue;
38 int time = Q[w].front().second - mt[w]; //选出最快完成服务的客户
39 if(time < 0) time = 0;
40 if(time < min_time){
41 min_time = time;
42 pos = w;
43 }
44 }
45 wt[pos] += Q[pos].front().second;
46 res[Q[pos].front().first] = wt[pos];
47 mt[pos] = 0;
48 Q[pos].pop();
49 for(int i=1; i<=n ;i++){ //其余窗口都要加上该时间
50 if(i!=pos) mt[i] += min_time;
51 }
52 if(cnt <= tot){
53 int id = n*m + cnt;
54 Q[pos].push(make_pair(id, line[cnt-1]));
55 cnt++;
56 }
57 }
58
59 while(q--){
60 int id; scanf("%d", &id);
61 if(res[id] - pt[id] >= 540){
62 printf("Sorry");
63 }
64 else{
65 int hour = 8 + res[id] / 60;
66 int mintues = res[id] % 60;
67 printf("%02d:%02d", hour, mintues);
68 }
69 printf("\n");
70 }
71
72 return 0;
73 }