題意#
這題說你有一根長度為 \(x\) 的木棍，想要把它切成 \(n\) 段指定長度的小木棍。
每次切割一根木棍時，花費的成本就是那根木棍「切之前的長度」。
請找出達成目標所需的最小總成本。
思路#
如果照著題目的順序思考「怎麼切」，情況會變得非常複雜。
這類問題通常可以反向思考。
也就是把「切木棍」變成「黏木棍」。
想像現在地上散落著 \(n\) 根小木棍。
我們每次挑兩根黏在一起，直到剩下最後一根長度為 \(x\) 的大木棍。
黏合的成本，就是那兩根木棍的總長度。
要讓總計成本最小，這其實是一個標準的貪婪演算法套用場景，概念類似霍夫曼樹（Huffman Tree）。
我們每次都貪心地挑選當下「最短的兩根木棍」來合併。
這樣長度較長的木棍就不會被重複計算太多次。
實作上，只要開一個 Min-Heap（在 C++ 就是 priority_queue 搭配 greater）。
不斷抽出最小的兩個數字相加，再把總和塞回 Heap 裡。
直到只剩下一個元素就算完成了。
程式碼#
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define INF LONG_LONG_MAX/1000
#define WA() cin.tie(0)->sync_with_stdio(0);
#define all(x) (x).begin(), (x).end()
#define int long long
#define PII pair<int, int>
signed main() { WA();
int n, x, t, sum = 0; cin >> x >> n; // x 為初始總長度，n 為最終小木棍數量
// 建立 Min-Heap (最小優先佇列)，確保每次 pop 出來的都是最小的元素
priority_queue<int, vector<int>, greater<int>> pq;
// 讀入每根小木棍的目標長度，並把它們全部丟進 Min-Heap 裡
while (n--) cin >> t, pq.push(t);
// 不斷合併，直到只剩下一根大木棍為止
while (pq.size() != 1) {
// 取出當前最短的兩根木棍
int a = pq.top(); pq.pop();
int b = pq.top(); pq.pop();
// 將合併成本加到總計成本中
sum += a+b;
// 將合併後的新木棍放回 Min-Heap 參與後續的合併
pq.push(a+b);
}
cout << sum;
}
