合并果子 编程题

题目大意：

在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。
每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过n-1次合并之后，就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。

解题思路：

有两种方法，一个是不停快排（归并），堆应该是比快排（归并）更优的解。
这里提供的是利用堆的AC代码~

#include//万能库不用说了
#define INF 2147483648/4//万能赋值（只是懒得打）
using namespace std;
long long n,a[10001],x,y,sum,m,p;
void up(int x)//上移操作
{
    while(x>1&&a[x]a[y+1])  y++;
        swap(a[y],a[x]);
        x=y; y=x*2;
     }
}

int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
        scanf("%d",&a[i]),up(i);//建堆
    while(n>1)//如果节点数大于1就继续合并~
    {
        int w=a[1]; a[1]=a[n]; n--; down(1);
        w+=a[1]; a[1]=a[n]; n--; down(1);
        n++; a[n]=w; sum+=w; up(n); 
    }
    printf("%d\n",sum);//输出一共需要多少体力~
    return 0;
}