题解 | #搬水果#

哈夫曼树

#include<iostream>
#include<queue>
using namespace std;

int main(){
  int n;
  while(scanf("%d",&n)!=EOF){
    if(n==0)break;
    priority_queue<int, vector<int>, greater<int> >H;//小根堆的优先队列
    while(n--){
      int x;
      scanf("%d",&x);
      H.push(x);
    }
    int ans=0;
    while(H.size()>1){
      int a=H.top();
      H.pop();
      int b=H.top();
      H.pop();
      ans+=a+b;//累加非叶子结点
      H.push(a+b);//新节点入队
    }
    printf("%d\n",ans);
  }
  return 0;
}