1014 Waiting in Line
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.
Input Specification:
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.
Sample Input:
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 个窗口前的队伍都排满时，第 NM+1 个顾客以及以后的顾客只能在黄线以外的区域等候。黄线外的所有客户统一排成一个长队。
每当客户进入黄线以内时，他会选择到当前排队人数最少的窗口处排队等待办理业务。当多个窗口前排队人数最少时，客户会选择窗口编号更小的窗口处排队等待办理业务。
第 i 名客户的办理业务时长为 Ti 。
最开始的 N 名客户将于早上 08:00 被受理业务。
现在，给定所有客户办理业务所需的时间，并对你进行若干次询问，每次询问一名客户办理完自身业务时的确切时间。
注意： 银行刚开始营业的时候黄线内时已经排满了人，而不是等到营业开始后客户才去一个个的选择。
思路
这道题如果取枚举每一秒的话时间复杂度会很大，所以我们可以去枚举每一个客户服务结束的时间，每个窗口都用一个队列来维护，存的就是该窗口前排队的客户的服务结束时间。具体步骤如下：
1.遍历每一个客户，选择一个最佳窗口。
2.计算该窗口加上该客户后服务的结束时间，并更新该窗口维护的客户结束时间，如果该客户进来前黄线内已满，则要将该窗口队头的客户移出即队头客户已经结束了该客户才进黄线内到这个窗口排队。
3.用哈希表记录每个客户的结束时间，注意服务的开始时间必须小于下午 5:00 。
4.询问客户的服务结束时间，由于哈希表中记录的时间是用分钟表示，所以还需要进行时间的转化。
代码
#include<bits/stdc++.h> using namespace std; const int N = 20; int n, m, k, Q; int sum[N]; unordered_map<int, int> h; queue<int> q[N]; int main() { cin >> n >> m >> k >> Q; //遍历每一个客户 for (int i = 1; i <= k; i++) { int s; cin >> s; //选择最佳窗口 int t = 0; for (int j = 0; j < n; j++) if (i <= n * m) //如果黄线内还没满，则可以在窗口前排队 { //找到排队人数最少的窗口，如果人数相同选择最左窗口 if (q[j].size() < q[t].size()) t = j; } else //如果黄线内人数已满，则要找到最早结束的窗口 { //每个队头存的是该窗口第一个人的结束时间 if (q[j].front() < q[t].front()) t = j; } sum[t] += s; //计算该窗口服务的结束时间 if (i > m * n) q[t].pop(); //将最早结束的那个客户从该窗口去掉 q[t].push(sum[t]); //往该窗口加入当前客户 if (sum[t] - s < 540) h[i] = sum[t]; //只能5点前办理新业务 } //开始询问 while (Q--) { int x; cin >> x; if (h.count(x)) printf("%02d:%02d\n", h[x] / 60 + 8, h[x] % 60); else puts("Sorry"); } return 0; }
