PAT 1014 Waiting in Line：銀行排隊模擬 (優先隊列 / 多隊列)

題目大意

N 個窗口 (N≤20)，每窗口黃線內最多排 M 人 (M≤10)。K 個顧客 (K≤1000) 依次到達，選最短隊列 (同長選號小)。前 N×M 人進入黃線內，其餘在黃線外等待。每人辦理時間 T[i]。求 Q 個查詢顧客的完成時間 (格式 HH:MM)，超過 17:00 輸出 Sorry。

模擬邏輯

1. 初始化： 前 `min(K, N*M)` 人按輪詢分配到窗口隊列 (模擬選最短隊列的等效過程)。記錄每人完成時間 `finish[i] = window_free_time[w] + T[i]`，更新窗口空閒時間。
2. 處理黃線外顧客： 對於第 `N*M+1` 到 K 個人：
   • 找到最早完成的窗口 (最小 `finish[front]`)。
   • 該窗口出隊一人，新顧客入隊。
   • 新顧客完成時間 = 該窗口當前空閒時間 + T[new]。
3. 查詢輸出： 若 `finish[id] - T[id] >= 540` (9小時=540分，即 17:00 前未開始) 輸出 Sorry，否則格式化輸出 `08:00 + finish[id]`。

代碼實現 (C++)

#include 
#include 
#include 
using namespace std;

const int MAXK = 1005;
const int INF = 0x3f3f3f3f;

int T[MAXK], finish[MAXK];
queue q[25];
int window_free[25];

int main() {
    int N, M, K, Q;
    scanf("%d%d%d%d", &N, &M, &K, &Q);
    for (int i = 0; i < K; i++) scanf("%d", &T[i]);
    
    // 初始分配：前 N*M 人輪詢入隊 (等價於每次選最短隊列)
    int idx = 0;
    for (int i = 0; idx < K && i < M; i++) { // 分 M 輪
        for (int w = 0; w < N && idx < K; w++) {
            q[w].push(idx);
            finish[idx] = window_free[w] + T[idx];
            window_free[w] = finish[idx];
            idx++;
        }
    }
    
    // 處理剩餘顧客
    for (; idx < K; idx++) {
        // 找最早完成的窗口
        int best_w = 0, min_finish = INF;
        for (int w = 0; w < N; w++) {
            if (!q[w].empty() && finish[q[w].front()] < min_finish) {
                min_finish = finish[q[w].front()];
                best_w = w;
            }
        }
        q[best_w].pop();
        q[best_w].push(idx);
        finish[idx] = window_free[best_w] + T[idx];
        window_free[best_w] = finish[idx];
    }
    
    // 回答查詢
    while (Q--) {
        int id; scanf("%d", &id); id--;
        if (finish[id] - T[id] >= 540) puts("Sorry");
        else {
            int h = 8 + finish[id] / 60;
            int m = finish[id] % 60;
            printf("%02d:%02d\n", h, m);
        }
    }
    return 0;
}

關鍵細節

• 初始分配用「輪詢 M 輪」完美模擬「每次選最短隊列，同長選小號」：前 N 人各佔一窗口，第 N+1 到 2N 人各佔第二位... 完全等價。
• 窗口空閒時間 `window_free[w]` 即隊列中最後一人的完成時間。
• 判斷 Sorry 條件：`start_time = finish - T >= 540` (17:00 = 8:00 + 540min)。注意是**開始時間**而非結束時間。
• 輸出格式 `%02d:%02d` 補零。