记录编号	420579	评测结果	AAAAAAAAAA
题目名称	[NOIP 2004]合并果子	最终得分	100
用户昵称	我只是个桐迷	是否通过	通过
代码语言	C++	运行时间	0.055 s
提交时间	2017-07-05 09:41:34	内存使用	0.39 MiB

#include <iostream>
#include <cstdio>
using namespace std;
const long long maxn=10090;
long long  dui[maxn];
long long n,chang=0,ans;
void charu(long long xinde);
long long  shanchu();
int main(){
	freopen("fruit.in","r",stdin);
	freopen("fruit.out","w",stdout); 
	cin>>n;
	for(int i=0;i<n;i++){
		long long x;
		cin>>x;
		charu(x);
	}
	for(int i=0;i<n-1;i++){
		long long x,y;
		x=shanchu();
		y=shanchu();
		ans=ans+x+y;
		charu(x+y);
	}
	cout<<ans<<endl;
	return 0;
}
void charu(long long xinde){
	dui[++chang]=xinde;
	long long next=chang;
	for(;chang>1;){
		long long  f=next/2;
		if(dui[f]>dui[next]){
			swap(dui[f],dui[next]);
		}
		else break;
		next=f;
	}
}
long long shanchu(){
	long long t=dui[1];
	dui[1]=dui[chang--];
	for(long long next=1;;){
		long long left=next*2;
		if(left>chang){
			break;
		}
		long long right=left+1,p=left;
		if(right<=chang){
			if(dui[right]<dui[left]){
				p=right;
			}	
		}
		if(dui[next]>dui[p]){
			swap(dui[next],dui[p]);
		}
		next=p;
	}
	return t;
}