小根堆维护一下就好了。
#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; }