题解 | #[NOIP2004]合并果子#

这道题可以用二叉堆做。 每次从二叉堆里拿最小的两堆果子，合并后，记录成本，并且把新的堆加入。循环直至仅剩1堆即可。

#include<bits/stdc++.h>
using namespace std;

using LL=long long;

#define SMA
#ifdef SMA
#define sym <
#else
#define sym >
#endif

template<typename datatype,const int size>class bheap{//sma root example
    public:
    int n;
    int heap[size];
    bheap(){
        n=0;
    }
    void up(int p){
        while(p>1){
            if(heap[p] sym heap[p/2]){//small root failed ,son < par
                swap(heap[p],heap[p/2]);
                p/=2;
            }else{
                break;
            }
        }
    }
    void insert(int val){
        heap[++n]=val;
        up(n);
    }
    void down(int p){
        int son=p*2;//point to left child
        while(son<=n){//in legal area
            if(son<n&&heap[son]>heap[son+1]){//choose smaller son
                ++son;
            }//choose lchild or right child
            if(heap[son]<heap[p]){//parent > smallest son
                //!fail to adapt to small root!
                swap(heap[son],heap[p]);
                p=son;son=2*p;
                //update
            }else{
                break;
            }
        }
    }
    void extract(){
        heap[1]=heap[n--];
        down(1);
    }
    int getTop(){
        return heap[1];
    }
    void remove(int k){
        heap[k]=heap[n--];
        up(k),down(k);
    }
};

int main(){
#ifdef LOCAL
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
    int n;
    cin>>n;
    bheap<int,10005> sheap;
    int tem;
    
    for(int in=0;in<n;++in){
        cin>>tem;
        sheap.insert(tem);
    }
    long long ans=0;
    while(sheap.n>=3){
        int temval=0;
        if(sheap.heap[2]<sheap.heap[3]){
            temval=sheap.heap[2]+sheap.heap[1];
            ans+=temval;
            sheap.remove(2);
            sheap.extract();
            sheap.insert(temval);
        }else{
            temval=sheap.heap[3]+sheap.heap[1];
            ans+=temval;
            sheap.remove(3);
            sheap.extract();
            sheap.insert(temval);
        }
    }
    if(sheap.n==2){
        int temval=sheap.heap[2]+sheap.heap[1];
        ans+=temval;
        sheap.remove(2);
        sheap.extract();
        sheap.insert(temval);
    }
    
    cout<<ans;
}