AcWing 148. 合并果子
原题链接
简单
作者:
我是java同学
,
2023-02-05 18:08:10
,
所有人可见
,
阅读 161
Huffman树 贪心
- 每一个合并过程对用一棵二叉树
- 每个叶节点对于最终的贡献 = 叶节点*到根节点的距离、
- 每次值需要合并最小的两堆的集合即可
- 可以用小根堆来维护每次取、删、插入最小值的操作
- 时间复杂度$o(nlogn)$
- 思路:每次取出小根堆里的两堆最少的果子,求出代价,再把合并后的果子放入小根堆里
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int main()
{
int n;
cin >> n;
priority_queue<int, vector<int>, greater<int>> heap;
while (n -- )
{
int x;
cin >> x;
heap.push(x);
}
int res = 0;
while (heap.size() > 1)
{
int a = heap.top(); heap.pop();
int b = heap.top(); heap.pop();
res += a + b;
heap.push(a + b);
}
cout << res << endl;
return 0;
}