立志用最少的代码做最高效的表达
PAT甲级最优题解——>传送门
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.
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
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
题意：K个人，N个窗口，每个窗口分为黄线内和黄线外， 每个窗口黄线内可以站M个人。
最初按窗口顺序在黄线里排队，如果黄线里排满，则统一排到黄线外（只有一个队列）。
当某一窗口有一个人办理完业务，黄线外的第一个人立刻补充到该窗口黄线内的队伍里。
老老实实写模拟即可。
解题思路：由于最后需要按编号查询， 因此定义结构体，元素有编号、所需时间、完成时间等等。然后定义结构体队列， 将时间简化为分钟，一分钟一次循环， 接下来对每个队列进行操作即可。
细节：
- 如果K<M*N， 那么入队列的人以K为准
- 如果到了17点，顾客还没有被服务(注意是被服务)。 那么输出sorry
（PS：抱着Debug的决心敲得代码，反反复复调试确认了很久才提交代码，结果一遍过，太开心了！）
#include<bits/stdc++.h>
using namespace std;
struct costomer{
int id, n_t1, n_t2, f_t; //编号、所需时间、实际完成时间
int h, m; //完成的小时数，分钟数
};
bool cmp(costomer c1, costomer c2) {
return c1.id < c2.id; //id号升序排列
}
int main() {
int N, M, K, Q; cin >> N >> M >> K >> Q;
queue<costomer>q[N];
int id = 1;
//处理前M*N个顾客
int Min = min(M, K);
while(1) {
for(int j = 0; j < N; j++) {
costomer cos;
int t; cin >> t;
cos.id = id++;
cos.n_t1 = cos.n_t2 = t;
q[j].push(cos);
if(id > min(M*N, K)) goto loop; //满足条件则退出循环
}
}
loop : ;
int now_cos_num = max(K-M*N, 0); //剩余未处理的乘客
vector<costomer>fin; //存放结果
int t = 0;
while(1) { //每次循环都是一分钟
t++;
int temp = 0;
for(int i = 0; i < N; i++) { //每一分钟所有窗口同时-1
if(!q[i].empty()) { //如果队列非空
q[i].front().n_t1--;
if(q[i].front().n_t1 == 0) { //如果剩余处理时间为0
q[i].front().f_t = t; //压入结果队列
costomer cos = q[i].front();
q[i].pop();
fin.push_back(cos); //结果序列存放该顾客
if(now_cos_num-- > 0) { //如果还有剩余顾客
int x; cin >> x; //输入，压入队列
cos.id = id++; cos.n_t1 = cos.n_t2 = x; cos.f_t = 0;
q[i].push(cos);
}
}
} else { //如果空了，代表没有后续的人，temp++。
temp++;
}
}
if(temp == N) break; //如果temp=窗口数，则说明无人，返回。
}
sort(fin.begin(), fin.end(), cmp);
for(int i = 0; i < Q; i++) {
int x; cin >> x; x-=1;
if(fin[x].f_t-fin[x].n_t2 >= 540) cout << "Sorry\n";
else printf("%02d:%02d\n", fin[x].f_t/60+8, fin[x].f_t%60);
}
return 0;
}