[杂七杂八] bzoj1724[Usaco2006 Nov]Fence Repair 切割木板

#include <iostream>#include <cstring>#include<cstdio>#define fo(i,a,b) for(int i=a;i<=b;i++)using namespace std;int heap[100001],sz=0;typedef long long ll;int n;inline void put(int y){    heap[++sz]=y;    int x=sz;    while (x>1&&heap[x>>1]>heap[x])    {        swap(heap[x],heap[x>>1]);        x>>=1;    }}inline int get(){    int t=heap[1];    heap[1]=heap[sz--];    int x=1;    while (x<=(sz>>1))    {        int next=x<<1;        if (next<sz&&heap[next|1]<heap[next])next++;        if (heap[next]>=heap[x])return t;        swap(heap[next],heap[x]);        x=next;    }    return t;}int main(){    scanf("%d",&n);    fo(i,1,n)    {        int x;        scanf("%d",&x);        put(x);    }    ll ans=0;    fo(i,1,n-1)    {        int x=get(),y=get();        put(x+y);        ans+=x+y;    }    printf("%lld\n",ans);    return 0;}