P1090 [NOIP2004 提高组] 合并果子

原题链接

题解

每次从所有果子堆中选重量最小的两堆并累加，观察到只需要找出 最小 因此考虑用堆

代码

#include<bits/stdc++.h>
using namespace std;

int pile[10005]={0};
int len=0;


void in(int x)
{
    pile[++len]=x;

    int now=len;
    while(pile[now]<pile[now/2]&&now>1)
    {
        swap(pile[now],pile[now/2]);
        now/=2;
    }
}

int out()
{
    swap(pile[len--],pile[1]);

    int son=2;
    while(son<=len)
    {
        if(son+1<=len&&pile[son+1]<pile[son])
        {
            son+=1;
        }
        if(pile[son]<pile[son/2]) swap(pile[son],pile[son/2]);
        else break;
        son*=2;
    }
    return pile[len+1];
}

int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        int x;
        scanf("%d",&x);
        in(x);
    }

    int ans=0;
    while(len>1)
    {
        int sum=out()+out();
        ans+=sum;
        in(sum);
    }

    printf("%d",ans);
    return 0;
}