记录编号	127347	评测结果	AAAAAAAAAA
题目名称	[NOIP 2004]合并果子	最终得分	100
用户昵称	rpCardinal	是否通过	通过
代码语言	C++	运行时间	0.019 s
提交时间	2014-10-15 15:37:00	内存使用	0.44 MiB

#include <cstdio>
#include <climits>
#include <algorithm>
using namespace std;

int n,a[20010],b[20010],la,ra,lb,rb,i,x,y,z,ans;

int main()
{
    freopen("fruit.in","r",stdin);
    freopen("fruit.out","w",stdout);
    scanf("%d",&n);
    for (i=1;i<=n;++i) scanf("%d",a+i); ra=n;
    sort(a+1,a+n+1);
    for (i=1;i<n;++i)
    {
        x=y=z=INT_MAX;
        if (ra-la>=2) x=a[la+1]+a[la+2];
        if (ra>la&&rb>lb) y=a[la+1]+b[lb+1];
        if (rb-lb>=2) z=b[lb+1]+b[lb+2];
        if (x<=y&&x<=z) {la+=2; b[++rb]=x; ans+=x;}
        else if (y<=x&&y<=z) {++la; ++lb; b[++rb]=y; ans+=y;}
        else if (z<=x&&z<=y) {lb+=2; b[++rb]=z; ans+=z;}
    }
    printf("%d\n",ans);
    fclose(stdin); fclose(stdout);
    return 0;
}