立志用最少的代碼做最高效的表達(dá)

---

PAT甲級(jí)最優(yōu)題解——>傳送門

---

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個(gè)人，N個(gè)窗口，每個(gè)窗口分為黃線內(nèi)和黃線外， 每個(gè)窗口黃線內(nèi)可以站M個(gè)人。
最初按窗口順序在黃線里排隊(duì)，如果黃線里排滿，則統(tǒng)一排到黃線外（只有一個(gè)隊(duì)列）。
當(dāng)某一窗口有一個(gè)人辦理完業(yè)務(wù)，黃線外的第一個(gè)人立刻補(bǔ)充到該窗口黃線內(nèi)的隊(duì)伍里。

老老實(shí)實(shí)寫模擬即可。

解題思路：由于最后需要按編號(hào)查詢， 因此定義結(jié)構(gòu)體，元素有編號(hào)、所需時(shí)間、完成時(shí)間等等。然后定義結(jié)構(gòu)體隊(duì)列， 將時(shí)間簡(jiǎn)化為分鐘，一分鐘一次循環(huán)， 接下來(lái)對(duì)每個(gè)隊(duì)列進(jìn)行操作即可。

細(xì)節(jié)：

如果K<M*N， 那么入隊(duì)列的人以K為準(zhǔn)

如果到了17點(diǎn)，顧客還沒有被服務(wù)(注意是被服務(wù))。 那么輸出sorry

（PS：抱著Debug的決心敲得代碼，反反復(fù)復(fù)調(diào)試確認(rèn)了很久才提交代碼，結(jié)果一遍過(guò)，太開心了！）

---

#include<bits/stdc++.h> using namespace std;struct costomer{int id, n_t1, n_t2, f_t; //編號(hào)、所需時(shí)間、實(shí)際完成時(shí)間 int h, m; //完成的小時(shí)數(shù)，分鐘數(shù) }; bool cmp(costomer c1, costomer c2) {return c1.id < c2.id; //id號(hào)升序排列 }int main() {int N, M, K, Q; cin >> N >> M >> K >> Q;queue<costomer>q[N];int id = 1;//處理前M*N個(gè)顧客 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; //滿足條件則退出循環(huán) }}loop : ;int now_cos_num = max(K-M*N, 0); //剩余未處理的乘客 vector<costomer>fin; //存放結(jié)果 int t = 0;while(1) { //每次循環(huán)都是一分鐘 t++;int temp = 0; for(int i = 0; i < N; i++) { //每一分鐘所有窗口同時(shí)-1 if(!q[i].empty()) { //如果隊(duì)列非空 q[i].front().n_t1--;if(q[i].front().n_t1 == 0) { //如果剩余處理時(shí)間為0 q[i].front().f_t = t; //壓入結(jié)果隊(duì)列 costomer cos = q[i].front();q[i].pop();fin.push_back(cos); //結(jié)果序列存放該顧客if(now_cos_num-- > 0) { //如果還有剩余顧客 int x; cin >> x; //輸入，壓入隊(duì)列 cos.id = id++; cos.n_t1 = cos.n_t2 = x; cos.f_t = 0;q[i].push(cos);}}} else { //如果空了，代表沒有后續(xù)的人，temp++。 temp++; }}if(temp == N) break; //如果temp=窗口數(shù)，則說(shuō)明無(wú)人，返回。 }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; }

---

耗時(shí)：

---

????????——錯(cuò)過(guò)落日余暉，請(qǐng)記得還有漫天星辰。

總結(jié)

以上是生活随笔為你收集整理的【一遍过！！！】1014 Waiting in Line (30 分)（题意+分析）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。