2019ABC 2019-08-21 06:32:40
点我顶贴
收藏
删除
#include<bits/stdc++.h>
using namespace std;
int heap[20005];
int n,len;
void put(int x){
int now,next;
heap[++len]=x;
now=len;
while(now>1){
next=now>>1;
if(heap[next]>heap[now])swap(heap[next],heap[now]);
now=next;
}
}
int get(){
int res=heap[1],now,next;
heap[1]=heap[len--];
now=1;
while(now*2<=len){
next=now<<1;
if(now*2<n&&heap[next+1]<heap[next])next++;
if(heap[now]<=heap[next])return res;
swap(heap[next],heap[now]);
now=next;
}
return res;
}
int main(){
int x,y,score=0;
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&x);
put(x);
}
for(int i=1;i<n;i++){
x=get();
y=get();
score+=x+y;
put(x+y);
}
printf("%d",score);
return 0;
}