ZYF040 连接木棍的最低费用
ZYF040 连接木棍的最低费用
【算法标签】 贪心
【语法标签】 :cin/cout、for循环、while循环、vector、long long、优先队列(priority_queue)
有 根木棍(),第 根木棍的长度为 ,每个长度均为正整数()。
每次可以选择两根木棍 和 进行连接,连接的成本为 。连接后得到一根新木棍,长度为 ,放回木棍堆中。
重复上述过程,直到只剩下一根木棍。
求:最小的总连接成本。
输入格式:
- 第一行:一个整数
- 第二行: 个整数,表示每根木棍的长度
输出格式:
- 一个整数,表示最小的总成本
样例 1:
输入:
3
3 4 2
输出:
14解释:先连接 2 和 3(成本 5),得到长度 5 的木棍;再连接 5 和 4(成本 9)。总成本 = 5 + 9 = 14。
样例 2:
输入:
4
5 2 4 8
输出:
36解释:
- 连接 2 和 4(成本 6),木棍变为 [5, 6, 8]
- 连接 5 和 6(成本 11),木棍变为 [11, 8]
- 连接 8 和 11(成本 19),木棍变为 [19]
- 总成本 = 6 + 11 + 19 = 36
二、解题思路
数据规模分析
- : 的算法可行, 不可行。
- 长度 , 次累加后总成本可能较大,使用
long long更为安全。
为什么是贪心?
本题与"合并果子"完全等价——连接木棍就是合并两堆。
核心原理:每次选择最短的两根木棍连接,总成本最小。
为什么?因为一根木棍在后续的连接中会被反复累加。如果一根很长的木棍很早就被连接,它的长度会在后面每一步中都贡献一次成本。因此,短木棍应该先连接(多贡献几次),长木棍应该后连接(少贡献几次)。
为什么不用 DP?
这题看起来像是"区间合并"类问题,可能会让人想到区间 DP。
但区间 DP 的前提是只能合并相邻的元素(如石子合并问题)。本题没有相邻限制,可以任意选择两根合并——这正是贪心能解决的信号。
判断标准:如果可以任意选两个合并(不需要相邻),就用贪心 + 优先队列;如果只能合并相邻的,就用区间 DP。
数据结构:小根堆
需要反复取出最小的两根、插入一根新的。用小根堆(priority_queue<int, vector<int>, greater<int>>)最合适:
- 取最小值:(堆顶)
- 删除最小值:
- 插入新值:
手动模拟样例
样例 1: n=3, sticks=[3, 4, 2]
| 步骤 | 当前木棍 | 操作 | 成本 | 累计成本 |
|---|---|---|---|---|
| 初始 | [2, 3, 4] | — | — | 0 |
| 第 1 次 | [2, 3, 4] | 连接 2+3=5 | 5 | 5 |
| 第 2 次 | [4, 5] | 连接 4+5=9 | 9 | 5+9=14 |
| 结束 | [9] | 只剩一根 | — | 14 |
样例 2: n=4, sticks=[5, 2, 4, 8]
| 步骤 | 当前木棍(堆序) | 操作 | 成本 | 累计成本 |
|---|---|---|---|---|
| 初始 | [2, 4, 5, 8] | — | — | 0 |
| 第 1 次 | [2, 4, 5, 8] | 连接 2+4=6 | 6 | 6 |
| 第 2 次 | [5, 6, 8] | 连接 5+6=11 | 11 | 6+11=17 |
| 第 3 次 | [8, 11] | 连接 8+11=19 | 19 | 17+19=36 |
| 结束 | [19] | 只剩一根 | — | 36 |
算法流程
- 将所有木棍长度加入小根堆。
- 循环 次:
- 弹出最小的两根,设长度为 和
- 累加成本
- 将 作为新木棍放回堆中
- 输出累计成本。
三、参考代码
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
// 小根堆:堆顶是最小值
priority_queue<int, vector<int>, greater<int>> pq;
// 读入所有木棍长度
for (int i = 1; i <= n; i++) {
int x;
cin >> x;
pq.push(x);
}
long long ans = 0; // 总成本可能较大,用 long long
// 进行 n-1 次连接
while (pq.size() > 1) {
// 取出最短的两根
int a = pq.top(); pq.pop();
int b = pq.top(); pq.pop();
// 连接
int sum = a + b;
ans += sum;
// 新木棍放回
pq.push(sum);
}
cout << ans << endl;
return 0;
}四、复杂度分析
- 时间复杂度:。初始将 个元素加入堆,(若逐个 push 则为 ,差别不大)。之后进行 次合并,每次合并需要 2 次
pop()和 1 次push(),每次 。因此总复杂度为 。 - 空间复杂度:。优先队列最多同时存储 个元素。
五、易错点
用大根堆而不是小根堆:默认的
priority_queue<int>是大根堆(堆顶最大),必须显式指定greater<int>才是小根堆。用错方向会得到"每次选最长的两根",答案是错的。ans 用 int 溢出:虽然每根木棍长度 ,但 时,经过反复累加,总成本可能超过 。建议使用
long long。循环条件写错:合并 根木棍需要 次操作,循环条件是
pq.size() > 1(堆中至少还有两根),写成pq.size() > 0会导致最后一次pop()空堆。
类似题目:B1752 合并果子(完全相同的模型,只是场景从"果子"变成了"木棍")。
