思路:按照树的思想考虑合并,树的最底层进行合并时需要计算的次数最多,所以质量最小的两个果子应该在树的最底层,最终所有果子合并到树的根节点,根节点的值即为消耗的体力和。将所有果子质量存入堆中(实现排序),每次挑出质量最小的两堆果子(堆顶的两个元素)合并,将总体力数加上这两堆果子的质量,将新合并成的果子堆的质量存入堆中(作为新的树的节点),这样就能实现合并消耗的总体力最小
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
int main()
{
int n;
priority_queue<int , vector<int>, greater<int>>heap;//用优先队列实现对所有果子的质量排序的操作
cin>>n;
while(n -- ){
int a;
cin>>a;
heap.push(a);
}
int res = 0;//记录答案
while(heap.size() > 1){//当树的节点数大于1,代表果子还没合并完
//取出当前最小的两个果子
int a = heap.top(); heap.pop();
int b = heap.top(); heap.pop();
res += a + b;//合并消耗的体力加上a和b的质量
heap.push(a + b);//将这两个果子合并,合并后的质量和作为新的节点加入树上
}
cout<<res<<endl;
return 0;
}