A21705 题解

很显然，这是一道哈夫曼树的基础题：

#include<bits/stdc++.h>
using namespace std;
struct f{
    int w;
    bool operator<(const f &b)const{ //运算符重载以实现小根堆
        return w>b.w;
    }
}a[20005];
priority_queue<f> q;
int n,sum;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i].w;
        q.push(a[i]);
    }
    while(q.size()>1){
        f x=q.top();q.pop();
        f y=q.top();q.pop();
        f xy;xy.w=x.w+y.w;
        sum+=xy.w;
        q.push(xy);
    }
    cout<<sum;
}