UVA 10954：Add All——最小合併代價（哈夫曼思想）

題目描述

給定 N 個正整數，每次挑兩個數相加，代價為兩數之和，將和放回集合。重複直到剩一個數，求最小總代價。

樣例

輸入：
3
1 2 3
4
1 2 3 4
0

輸出：
9
19

貪心策略：每次合併最小的兩個數

等價於哈夫曼編碼構建最優前綴碼，使用 最小堆（優先隊列） 實現：

1. 所有數入最小堆
2. 重複：取出最小兩數 a、b，累加 a+b 到答案，將 a+b 重新入堆
3. 堆剩一個元素時結束

C++ 實現

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

int main() {
    int n;
    while (scanf("%d", &n) == 1 && n) {
        priority_queue<int, vector<int>, greater<int>> pq;
        for (int i = 0, x; i < n; ++i) {
            scanf("%d", &x);
            pq.push(x);
        }
        long long 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);
        }
        printf("%lld\n", ans);
    }
    return 0;
}

複雜度

• 時間：O(N log N)
• 空間：O(N)

證明直覺

較小的數參與合併次數越多，總代價越小。最小堆確保每次選擇當前最小的兩個數，符合貪心選擇性質。