HDU 1873 完整解析：多優先級佇列模擬醫生診療

三位醫生並行，病人有優先級（10 最高，1 最低）。IN A B：優先級 B 病人掛醫生 A。OUT A：醫生 A 診療一位病人（選優先級最高、最早掛號者）。輸出被診療病人編號，無病人輸出 EMPTY。

資料結構：每醫生一個優先級佇列

佇列元素：{priority, reg_time, id}。
比較器：優先級大者優先，相同則掛號時間早者優先（reg_time 小優先）。

關鍵技巧：暫存彈出元素

OUT A 時，需從醫生 A 的佇列取最高優先級。若直接 pop 發現不是該醫生（不可能，佇列已按醫生分離），但原作者用單佇列+暫存實現。
正確做法：三個獨立 priority_queue，OUT 直接取頂。

完整 AC 程式碼（修正版：三獨立佇列）

#include <bits/stdc++.h>
using namespace std;

struct Patient {
    int prio, time, id;
    bool operator<(const Patient& o) const {
        if (prio != o.prio) return prio < o.prio; // 大優先級在頂
        return time > o.time; // 早掛號在頂
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N;
    while (cin >> N) {
        array, 4> qs; // 1~3 號醫生
        int reg_time = 0;
        
        for (int i = 0; i < N; i++) {
            string op; cin >> op;
            if (op == "IN") {
                int doc, prio; cin >> doc >> prio;
                qs[doc].push({prio, ++reg_time, reg_time}); // id = reg_time
            } else { // OUT
                int doc; cin >> doc;
                if (qs[doc].empty()) {
                    cout << "EMPTY\n";
                } else {
                    cout << qs[doc].top().id << '\n';
                    qs[doc].pop();
                }
            }
        }
    }
    return 0;
}

原作者單佇列暫存法（理解思路）

// 原始邏輯：單佇列存所有病人，OUT 時彈出檢查醫生號
// 不匹配者暫存到另一佇列，匹配者輸出，最後把暫存倒回
// 此法效率較低且易錯，推薦上方三獨立佇列法

關鍵點總結

• 三獨立優先級佇列：按醫生分離，OUT 直接 O(log N) 取頂
• 比較器雙關鍵字：優先級降序、掛號時間升序
• 病人編號 = 掛號序號：單調遞增計數器
• 多測資 EOF 結束：while(cin >> N)