POJ 3253 Fence Repair：哈夫曼樹優先隊列經典實現

題目大意

農夫約翰需將長木板鋸成 N 塊指定長度。每次鋸切花費等於當前木板長度。求最小總花費。N ≤ 20,000，長度 ≤ 50,000。

解題思路

經典哈夫曼樹構建：每次合併最小的兩塊木板，花費為兩者之和。使用最小堆（優先隊列）實現。

演算法步驟

1. 讀入 N 和 N 個長度
2. 所有長度入最小堆
3. 堆大小 > 1 時：取出最小兩個 p1, p2，合併 temp = p1+p2，累加答案，temp 入堆
4. 輸出總花費

關鍵點

• C++ priority_queue 默認大根堆，需自定義比較器或用 greater<int> 實現小根堆
• 答案可能超過 32 位，使用 long long
• 貪心正確性源於哈夫曼編碼最優前綴碼性質

完整代碼

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

typedef long long ll;

int main() {
    int N;
    while (cin >> N) {
        priority_queue<int, vector<int>, greater<int>> pq;
        for (int i = 0; i < N; i++) {
            int x; cin >> x;
            pq.push(x);
        }
        ll ans = 0;
        while (pq.size() > 1) {
            int a = pq.top(); pq.pop();
            int b = pq.top(); pq.pop();
            ans += a + b;
            pq.push(a + b);
        }
        cout << ans << endl;
    }
    return 0;
}

複雜度分析

N 次插入、2(N-1) 次取出、N-1 次插入，每次 O(log N)，總時間 O(N log N)，空間 O(N)。