HDU 1896 Stones：優先隊列解題詳解

題目背景

HDU 1896 "Stones" 是一道經典的優先隊列應用題目。題目要求模擬一個拋石頭的過程：給定 n 顆石頭的初始位置和拋擲距離，每次從優先隊列中取出位置最小（位置相同時距離最小）的石頭，奇數次操作將石頭拋到新位置並放回隊列，偶數次操作直接移除石頭。最終輸出最後一次拋擲的落點位置。

核心思路

這道題的關鍵在於正確維護優先隊列的順序。根據題意，石頭的優先級規則為：

• 位置較小的石頭優先
• 位置相同時，拋擲距離較小的優先

這對應程式碼中的運算子重載：

friend bool operator <(node n1, node n2) {
    if (n1.pos == n2.pos) return n1.d > n2.d; // 距離從小到大
    return n1.pos > n2.pos; // 位置從小到大
}

演算法流程

1. 讀入測試案例數 t
2. 對每個案例，讀入石頭數量 n
3. 將 n 顆石頭的位置和距離存入優先隊列
4. 用計數器 num 記錄操作次數，奇數次拋擲並重新入隊，偶數次直接出隊
5. 記錄最後一次拋擲的落點位置 sum = a.pos + a.d
6. 隊列為空時輸出 sum

複雜度分析

每顆石頭最多進出隊列一次，優先隊列操作的時間複雜度為 O(log n)，總體複雜度為 O(n log n)，空間複雜度為 O(n)，完全滿足題目要求。

完整代碼

#include <stdio.h>
#include <queue>
using namespace std;

struct node {
    int pos;
    int d;
    int num;
    friend bool operator <(node n1, node n2) {
        if (n1.pos == n2.pos) return n1.d > n2.d;
        return n1.pos > n2.pos;
    }
};

struct node a;

int main() {
    int t, n, i, num, sum;
    while (~scanf("%d", &t)) {
        while (t--) {
            priority_queue<node> q;
            scanf("%d", &n);
            num = 1;
            for (i = 0; i < n; i++) {
                scanf("%d%d", &a.pos, &a.d);
                q.push(a);
            }
            a = q.top();
            sum = 0;
            while (!q.empty()) {
                if (num % 2) {
                    a = q.top();
                    sum = a.pos + a.d;
                    a.pos = a.d + a.pos;
                    q.pop();
                    q.push(a);
                    num++;
                } else {
                    a = q.top();
                    q.pop();
                    num++;
                }
            }
            printf("%d\n", sum);
        }
    }
    return 0;
}