思路
本题是 哈夫曼树求最小的带权路径和 的思想:每次选择所有点中权值最小的两个点进行合并(合并完也要算作一个点)
举个例子就明白了:
粉红色
的叶节点就是我们原来的4堆果子,他们到根节点的路径长度就是 被合并(或者说被搬运)的次数
1和2被搬运了(哪怕是混在新的堆内被搬运)
3
次,消耗 = (1+2)*3 = 93被搬运了
2
次,消耗 3*2 = 64被搬运了
1
次,消耗 4*1 = 4
- 故总消耗就是19
用代码实现的时候可以用小根堆
来做:每次取出最小的两个元素,合并后再加进去,直到堆内只有一个元素,表示所有的果子都合并完成,期间用一个变量res累计消耗即可。
C++ 代码
#include <iostream>
#include <queue>
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();
heap.push(a + b);
res += a + b;
}
cout<<res<<endl;
return 0;
}