ZYF041 连接木棍的最小费用
大约 1 分钟贪心
ZYF041 连接木棍的最小费用
【算法标签】 贪心
【语法标签】 :cin/cout、for循环、while循环、vector、优先队列(priority_queue)
- 时间复杂度:(O(n \log n)),建堆 (O(n)),每次堆操作 (O(\log n)),共 (n-1) 次合并。
- 空间复杂度:(O(n)),优先队列存储所有木棍长度。
参考代码:
#include <bits/stdc++.h> // 万能头文件,包含所有C++标准库
using namespace std; // 使用标准命名空间,简化代码
int main(){
// 小根堆:堆顶永远是最小元素,保证每次取出的是当前最短的木棍
// greater<int> 表示升序排列,默认是大根堆
priority_queue<int,vector<int>,greater<int> > q;
int n,t;
cin >> n; // 输入数字个数
for(int i = 0;i < n;i++){
cin >> t; // 输入每个数字
q.push(t); // 插入小根堆
}
int sum = 0; // 记录总合并代价
// 堆中只剩 1 个元素时,合并完成
while(q.size() != 1){
int a = q.top(); // 取堆顶(最小数)
q.pop(); // 删除堆顶
int b = q.top(); // 取新堆顶(次小数)
q.pop();
sum += a + b; // 累加合并代价
q.push(a + b); // 把合并后的数放回堆
}
cout << sum; // 输出总代价
return 0;
}