题解 | #合并果子#

典型哈夫曼树问题
方法一：使用小根堆解决

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
priority_queue<int,vector<int>,greater<int>> q;
int main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin >> n ;
    for(int i=0;i<n;i++){
        int x;
        cin >> x;
        q.push(x);
    }
    int ans=0;
    for(int i=1;i<n;i++){//n-1次合并操作 
    //也可写成while(q.size()>1) 
        int x=q.top();
        q.pop();
        int y=q.top();
        q.pop();
        ans+=x+y;
        q.push(x+y);
    }
    cout << ans ;
    return 0;
}

方法二：用数组手动写堆

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
int a[10010];
int tot=0;
void push(int x){
    tot++;
    a[tot]=x;
    int i=tot;//er
    int j=i/2;//fu
    while(j>0 && a[i]<a[j]){//j>0防止父亲结点出界 
        swap(a[i],a[j]);
        i=j;
        j=i/2;
    }
}
int top(){
    return a[1];//数组a从1开始放 
}
void pop(){
    a[1]=a[tot--];
    int i=1;//fu
    int j=i*2;//er
    if(j+1<=tot && a[j+1]<a[j])    j++;//j指向两个孩子中的较小者
    while(j<=tot && a[i]>a[j]){//j<=tot防止父亲结点出界
        swap(a[i],a[j]);
        i=j;
        j=i*2;
        if(j+1<=tot && a[j+1]<a[j])    j++;//j指向两个孩子中的较小者
    } 
}
int main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin >> n ;
    for(int i=0;i<n;i++){
        int x;
        cin >> x;
        push(x);
    }
    int ans=0;
    for(int i=1;i<n;i++){//n-1次合并操作 
        int x=top();
        pop();
        int y=top();
        pop();
        ans+=x+y;
        push(x+y);
    }
    cout << ans ;
    return 0;
}