题目描述

在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。
每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过n-1次合并之后，就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。
因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为1，并且已知果子的种类数和每种果子的数目，你的任务是设计出合并的次序方案，使多多耗费的体力最少，并输出这个最小的体力耗费值。
例如有3种果子，数目依次为1，2，9。可以先将1、2堆合并，新堆数目为3，耗费体力为3。接着，将新堆与原先的第三堆合并，又得到新的堆，数目为12，耗费体力为12。所以多多总共耗费体力=3+12=15。可以证明15为最小的体力耗费值。

输入描述:

输入包括两行，第一行是一个整数，表示果子的种类数。第二行包含n个整数，用空格分隔，第i个整数是第i种果子的数目。

输出描述:

输出包括一行，这一行只包含一个整数，也就是最小的体力耗费值。输入数据保证这个值小于231。

示例1

输入
3
1 2 9
输出
15

备注

对于30％的数据，保证有；
对于50％的数据，保证有；
对于全部的数据，保证有。

解答

这道题只需要把最小的两个果堆加起来就可以了，好多大佬都用的是优先队列，但由于本人太菜，只好用数组做。
如果这样想，那么每合并一次都需要排一次序，但事实上并不需要这么做（而且这样会超时，我之前用sort函数排就过了四个点，后面全都tle了），只需要给新合并的果堆找到所在的位置，并且将空的果堆删除就可以了。
下面AC代码。 
 #include<bits/stdc++.h>//（万能库）
 using namespace std;
 int a[100000];//(用一个数组来代替队列)
 int main(){
 int n,sum=0;
 cin>>n;
 for(int i=1;i<=n;i++) {
    cin>>a[i];//（读入数据）
    }
    sort(a+1,a+n+1);//（初始排序）
    while(1){//（开始合并循环，其实可以用for代替）
        int j=1;
        while(a[j]==0)
        j++;
        //（其实这里懒了，当时做的时候用的是sort,可以用别的做法）
        if(j==n) break;//（此时只存在一个堆，退出循环）
        else {
            a[j]+=a[j+1];
            sum+=a[j];//（i和j 合并成一个果堆，增加所用的力气）
            for(int l=j+1;l<n;l++)
             {
                a[l]=a[l+1];//（将j后面的果堆向前一位）
            }
            n--;//（减少一个堆）
        }
        for(int l=j;l<n;l++)
        {
            if(a[l]>a[l+1])//（为新的堆找到位置）
            {
                swap(a[l],a[l+1]);
            }
        }
    }
    cout<<sum;//（输出力气）
    return 0;//（功德圆满）
  }


来源：chengni