POJ 3253 Fence Repair：霍夫曼編碼思想求最小切割成本

題目大意

有一根長度為 L 的木板，需切成 n 塊指定長度。每次切割成本等於當前木板長度。求最小總成本。

核心洞察：霍夫曼樹 / 貪心合併

逆向思考：切割過程構成一棵二叉樹，葉子為目標木板，內部節點為合併後的木板。總成本 = Σ(葉子長度 × 深度)。為最小化總成本，最短木板應對應最深節點 → **每次合併最短的兩塊木板**（霍夫曼編碼原理）。

算法流程

1. 將所有目標長度放入**最小堆**（優先隊列）。
2. 重複：取出最小的兩塊 l1, l2，成本累加 l1+l2，將 l1+l2 放回堆。
3. 直到堆中只剩一塊，累加成本即為答案。

完整代碼

#include <iostream>
#include <queue>
#include <vector>
#include <functional>
using namespace std;
typedef long long LL;
const int N = 20000 + 10;
int d[N];
int n;
LL ans;
void solve() {
    priority_queue<int, vector<int>, greater<int>> q;
    for (int i = 0; i < n; i++) q.push(d[i]);
    while (q.size() > 1) {
        int l1 = q.top(); q.pop();
        int l2 = q.top(); q.pop();
        ans += l1 + l2;
        q.push(l1 + l2);
    }
    printf("%lld\n", ans);
}
int main() {
    while (~scanf("%d", &n)) {
        for (int i = 0; i < n; i++) cin >> d[i];
        ans = 0;
        solve();
    }
    return 0;
}

關鍵點

• 使用 greater<int> 實現最小堆（默認最大堆）。
• 長度和可能超過 int，用 long long 存儲答案。
• 輸入多組測試，以 EOF 結束。

複雜度

• 每次堆操作 O(log n)，共 n-1 次合併，總 O(n log n)。
• n ≤ 20000，極快。

延伸應用

霍夫曼編碼、最優合併模式、遊戲開發中資源合成成本優化等。