POJ 2051 / UVALive 3135 Argus：優先隊列模擬定時任務調度

題目大意

註冊若干查詢，每個有 ID (Q_num) 和周期 (Period)。所有查詢同時啟動，首次在 Period 秒後返回結果，之後每隔 Period 秒返回一次。輸出前 K 個返回結果的查詢 ID。同一時間按 ID 升序輸出。

優先隊列模擬

每個查詢用結構體存儲 {qnum, period, next_time}。
優先隊列按 next_time 升序，相同時按 qnum 升序。
初始將所有查詢推入隊列，next_time = period。
重複 K 次：取出堆頂，輸出 qnum，更新 next_time += period，重新入堆。

參考代碼 (C++)

#include <bits/stdc++.h>
using namespace std;
struct Query {
    int qnum, period, time;
    bool operator<(const Query& other) const {
        return time > other.time || (time == other.time && qnum > other.qnum); // 小頂堆
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string cmd;
    priority_queue pq;
    while (cin >> cmd, cmd != "#") {
        Query q; cin >> q.qnum >> q.period;
        q.time = q.period;
        pq.push(q);
    }
    int K; cin >> K;
    while (K--) {
        Query q = pq.top(); pq.pop();
        cout << q.qnum << '\n';
        q.time += q.period;
        pq.push(q);
    }
    return 0;
}

複雜度

每次堆操作 O(log N)，總時間 O((N+K) log N)，N ≤ 1000，K ≤ 10000，極快。