思路:因为每次只能将两堆合并成一堆(堆数-1),所以合并次数一定是n-1次.那么只要让每次合并消耗的体力值最小即可(永远选择最小的两堆).刚好符合最小堆优先队列

PS:注意stl中的优先队列默认是最大堆,不像sort()默认从小到大排序.想要最小堆,就要使用greater<>,并且在中间还要加上vector,符合STl库中priority_queue<>的传参顺序

AC代码(使用STL):

#include<queue>
#include<functional>
#include<iostream>
#include<algorithm>
using namespace std;
int fruit[10010];
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);
    int n;cin>>n;
    for(int i=1;i<=n;++i) {cin>>fruit[i];}
    sort(fruit+1,fruit+1+n);
    priority_queue<int, vector<int>, greater<int>> priqu;
    for(int i=1;i<=n;++i) {priqu.push(fruit[i]);}
    long long res=0,t1,t2;
    for(int i=1;i<n;++i)
    {
        t1=priqu.top();
        priqu.pop();
        t2=priqu.top();
        priqu.pop();
        t1+=t2;//即t1=t1+t2省的再开一个临时变量
        priqu.push(t1);
        res+=t1;
    }
    cout<<res;
    return 0;
}

AC代码:(手动实现优先队列)

要好好理解完全二叉树父子节点的关系

优先队列->二叉堆->特殊的完全二叉树

最大堆(父节点>=子节点),最小堆(父节点<=子节点)

因为优先队列仅要求队首 .top() 最大(最小),所以不需要每次都排序(复杂度爆表),故利用完全二叉树的性质(左子节点==父节点2,右子节点==父节点2+1)

#include<queue>
#include<iostream>
#include<algorithm>
#define I inline
using namespace std;
int fruit[10010],qu[10010],cnt=0;//cnt记录最后一个元素所在位置
I void push(int x)
{
  qu[++cnt]=x;
  int i=cnt,j=cnt>>1;// j/2向下取整,即找到父节点( (int)1/2==0)
  while(j!=0 && qu[j]>qu[i])//父节点存在(>=1或者说!=0),且父节点比子节点大
  {
      swap(qu[j],qu[i]);//那么就交换
      i>>=1;//i>>=1或者写i=j,把当前的父节点作为下一次遍历的子节点
      j>>=1;//或者写j=i>>1;//找到下次的父节点
  }
}
I int top()
{
  return qu[1];//返回队首
}
I void pop()
{
  qu[1]=qu[cnt];//移除队首元素,将队尾元素放到队首
  --cnt;
  int l=1,r=2;
  if(r+1<=cnt && qu[r+1]<qu[r]) {++r;}//找子节点中存在,并且更小的那个
  while(r<=cnt && qu[r]<qu[l])//如果子节点存在且子节点<父节点
  {
      swap(qu[r],qu[l]);//那么就交换
      l=r;//把当前的子节点作为下一次遍历的父节点,这里不确定2倍还是2倍+1,所以不能写<<1;
      r<<=1;//遍历到二叉树的下一层
      if(r+1<=cnt && qu[r+1]<qu[r]) {++r;}//找子节点中存在,并且更小的那个
  }
}
int main()
{
  ios::sync_with_stdio(0);cin.tie(0);
  int n;cin>>n;
  for(int i=1;i<=n;++i) {cin>>fruit[i];}
  sort(fruit+1,fruit+1+n);
  for(int i=1;i<=n;++i) {push(fruit[i]);}
  long long res=0,t1,t2;
  for(int i=1;i<n;++i)
  {
      t1=top();
      pop();
      t2=top();
      pop();
      t1+=t2;
      push(t1);
      res+=t1;
  }
  cout<<res;
  return 0;
}