您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> C++ 入門

UVA 10954 Add All 貪心算法：最小堆優化實現詳解

編輯：C++ 入門

UVA 10954 Add All - 貪心策略與優先隊列實現

題目要求反覆取出兩個最小數相加，將和放回，直到剩一個數。所有相加過程中產生的和的總和即為答案。這是經典的霍夫曼編碼/最優合併模式問題，貪心策略：每次合併最小的兩個數，總代價最小。

算法證明直觀理解

類比霍夫曼樹構建：將每個數視為葉子節點權重，每次合併對應創建父節點。越小的權重越早參與合併，累加的層數越多，對總代價貢獻越大。因此優先合併最小的兩個數能得到全局最優解。

優先隊列 (最小堆) 優化實現

#include 
#include 
using namespace std;

int main() {
    long long n, x;
    while (scanf("%lld", &n) != EOF && n) {
        priority_queue, greater> pq;
        for (int i = 0; i < n; i++) {
            scanf("%lld", &x);
            pq.push(x);
        }
        long long ans = 0;
        while (pq.size() > 1) {
            long long a = pq.top(); pq.pop();
            long long b = pq.top(); pq.pop();
            long long sum = a + b;
            ans += sum;
            pq.push(sum);
        }
        printf("%lld\n", ans);
    }
    return 0;
}