用优先队列维护,每次取出队列中的前连个元素,相加弹出再入队它们之和,每次更新消耗的体力值。
(哈夫曼树)
#include<bits/stdc++.h>
using namespace std;
priority_queue <int,vector<int>,greater<int>> heap;//优先队列,小根堆
int main()
{
int n;
cin>>n;
for(int i=0;i<n;i++)
{
int a;
cin>>a;
heap.push(a);
}
int res=0;
while(!heap.empty())
{
int a=heap.top();
heap.pop();
if(heap.empty())break;
int b=heap.top();
heap.pop();
int c=a+b;
res+=c;
heap.push(c);
}
cout<<res<<endl;
return 0;
}