NYOJ 55 懶省事的小明：哈夫曼樹思想與優先隊列求最小合併代價

題目大意

有 n 種水果，第 i 種有 a_i 個（每個重 1）。每次可合併兩堆，代價為兩堆重量之和。求合併成一堆的最小總代價。多組測試（n ≤ 12000，a_i ≤ 20000）。

核心洞察：哈夫曼樹 / 貪心策略

最優策略：每次合併當前最小的兩堆。這與哈夫曼編碼構建過程完全一致，證明可參考哈夫曼樹最優性證明（交換論證）。

數據結構：最小優先隊列

C++ priority_queue 默認大頂堆，需自定義比較器實現小頂堆：

priority_queue<long long, vector<long long>, greater<long long>> pq;

AC 代碼

#include <iostream>
#include <queue>
#include <vector>
#include <functional>  // greater
using namespace std;

typedef long long LL;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int T; cin >> T;
    while (T--) {
        int n; cin >> n;
        priority_queue<LL, vector<LL>, greater<LL>> pq;
        
        for (int i = 0; i < n; ++i) {
            LL x; cin >> x;
            pq.push(x);
        }
        
        LL ans = 0;
        while (pq.size() > 1) {
            LL a = pq.top(); pq.pop();
            LL b = pq.top(); pq.pop();
            LL sum = a + b;
            ans += sum;
            pq.push(sum);
        }
        cout << ans << '\n';
    }
    return 0;
}

樣例驗證

輸入：
1
3
1 2 9

過程：
合併 1+2=3，代價 3
合併 3+9=12，代價 12
總代價 = 15

輸出：15

複雜度分析

• 每次操作 O(log n)，共 n-1 次合併
• 總時間：O(n log n)
• 空間：O(n)
• long long 防溢出：最大 12000 × 20000 × log₂(12000) ≈ 3.3×10⁹，需 64 位

總結

經典哈夫曼樹應用：最小合併代價 = 每次取最小兩個合併。優先隊列（堆）是實現貪心策略的標準數據結構，代碼極其簡潔高效。