UVA 10588 Queuing at the Doctors：優先隊列模擬醫院排隊系統

題目大意

n 個病人、m 個醫生辦公室。每個病人有到達時間 t、需依序訪問 k 個辦公室。規則：

1. 到達時間 t 時出現在第一個辦公室隊列
2. 同一時刻同辦公室按編號小優先，接在已有隊列後
3. 每單位時間醫生處理隊首一人，處理完進入下一辦公室隊列（或離開醫院）
4. 求最後一人離開醫院的時間

模擬策略：每辦公室一個優先隊列

• 隊列元素：(當前可進入時間, 病人編號)
• 優先級：時間小優先，時間同則編號小優先
• 病人狀態：用 queue 存剩餘辦公室序列

算法流程

1. 讀入所有病人，按到達時間推入第一個辦公室的優先隊列
2. 時間推進循環 ans = 0：
   • 遍歷所有辦公室 i：
   • 若隊列非空且隊首 time ≤ ans：
   • 彈出病人，從其辦公室序列彈出當前辦公室
   • 若還有下一辦公室：time = ans + 1 推入下一辦公室隊列
   • 否則病人離開
3. 若所有隊列空，結束，輸出 ans - 1（最後一次遞增後多加 1）

代碼實現

#include <cstdio>
#include <queue>
#include <vector>
using namespace std;

const int MAXM = 1100;

struct Node {
    int t, id;  // 可進入時間, 病人編號
    bool operator<(const Node& o) const {
        if (t == o.t) return id > o.id;  // 小頂堆：時間小、編號小優先
        return t > o.t;
    }
};

priority_queue p[MAXM];  // 每個辦公室一個優先隊列
queue q[MAXM];            // 每個病人剩餘辦公室序列

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        int n, m; scanf("%d%d", &n, &m);
        for (int i = 0; i < m; ++i) while (!p[i].empty()) p[i].pop();
        for (int i = 0; i < n; ++i) {
            while (!q[i].empty()) q[i].pop();
            int t, k, x; scanf("%d%d", &t, &k);
            while (k--) { scanf("%d", &x); q[i].push(x - 1); }  // 0-based
            p[q[i].front()].push({t, i});
        }
        int ans = 0, flag = 1;
        while (flag) {
            flag = 0;
            for (int i = 0; i < m; ++i) {
                if (!p[i].empty()) {
                    flag = 1;
                    Node now = p[i].top();
                    if (now.t > ans) continue;  // 尚未到達時間
                    p[i].pop();
                    q[now.id].pop();  // 移除當前辦公室
                    if (!q[now.id].empty()) {
                        now.t = ans + 1;
                        p[q[now.id].front()].push(now);
                    }
                }
            }
            ans++;
        }
        printf("%d\n", ans - 1);
    }
    return 0;
}

關鍵細節

• 時間推進：ans 從 0 開始，每輪處理所有辦公室當前可服務的病人，然後 ans++
• 優先隊列比較：operator< 反向實現小頂堆（priority_queue 默認大頂堆）
• 病人狀態分離：辦公室隊列只存 (time, id)，具體辦公室序列存病人自己的 queue
• 終止條件：所有優先隊列為空

複雜度

• 總操作數 ≤ 1,000,000（題目保證）
• 每次隊列操作 O(log n)，總時間 O(總操作數 × log n)
• 空間 O(n + m + 總操作數)

此題將離散事件模擬轉化為多優先隊列協同，避免了逐時間步推進的低效，是經典的「多隊列醫院/銀行排隊」模擬範例。