HDU 1896 Stones：優先隊列模擬石頭移動問題解析

題目大意

直線道路上有 n 顆石頭，每顆石頭有初始座標 codr 與投擲距離 dis。人從起點出發依次遇到石頭：遇到第奇數顆石頭，將其向前拋擲 dis 距離並放回隊列；遇到第偶數顆石頭則保持原位。求人走到最後一顆石頭位置時，距離起點多遠。

解題思路

石頭的處理順序永遠依當前座標從小到大，故使用最小堆（優先隊列）維護石頭集合。模擬過程：

1. 將所有石頭按座標入隊。
2. 計數器 cnt 從 1 開始，每次取出堆頂石頭：
3. 若 cnt 為奇數，將石頭座標加上 dis 後重新入隊；
4. 若為偶數，石頭不再入隊（視為已處理完畢）。
5. cnt++，重複直到隊列為空。最後取出的石頭座標即為答案。

關鍵代碼（C++）

struct Stone {
    int codr, dis;
    bool operator<(const Stone& other) const {
        return codr > other.codr;  // 小頂堆
    }
};

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        int n; scanf("%d", &n);
        priority_queue<Stone> pq;
        for (int i = 0; i < n; ++i) {
            Stone s; scanf("%d %d", &s.codr, &s.dis);
            pq.push(s);
        }
        int cnt = 1, last = 0;
        while (!pq.empty()) {
            Stone cur = pq.top(); pq.pop();
            last = cur.codr;
            if (cnt & 1) {  // 奇數
                cur.codr += cur.dis;
                pq.push(cur);
            }
            ++cnt;
        }
        printf("%d\n", last);
    }
    return 0;
}

複雜度分析

• 時間：每顆石頭最多進出隊列 O(log n) 次，總體 O(n log n)。
• 空間：優先隊列存儲 O(n) 顆石頭。

總結

本題核心在於識別「動態有序集合」特徵，優先隊列完美契合。注意奇偶計數器的更新時機與石頭重入隊邏輯，即可正確模擬全過程。