合并石子(果子)（贪心算法）C++

石子(果子)（贪心算法）C++"/>

合并石子(果子)（贪心算法）C++

石子合并
时间限制: 1 Sec 内存限制: 128 MB

题目描述
现在有n堆石子，你每次可以挑任意两堆将其合并成一堆，消耗体力是两堆石子的数量和。可知经过n-1次合并后只剩下一堆石子，现在要求消耗总体力最小，请求出合并石子所消耗的最小总体力。

输入
第一行一个n(0 < n <= 10000)，代表有n堆石子，接下来一行n个由空格分隔的数ai(0 <= ai <= 100000)表示第i堆石子的数目。

输出
输出一行表示答案。

样例输入
5
1 2 3 4 5
样例输出
33

AC代码在最下面

刚开始的想法是用数组，每合并两堆之后便重新排序，结果时间超限，代码如下所示：

#include<iostream>
#include<vector>
#include<algorithm>
typedef unsigned long long llu;
using namespace std;int main()
{int i=0,n,a[100050];cin >> n ;while(i<n){cin >> a[i];i++;}llu s=0;sort(a,a+n);for(i=0;i<n-1;i++){a[i+1]+=a[i];s+=a[i+1];sort(a+i,a+n);}cout << s << endl ;
}

然后改为使用优先队列容器，能成功通过测试，代码如下:

#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
typedef unsigned long long llu;
using namespace std;int main(){priority_queue<llu,vector<llu>,greater<llu> >x;//创建一个升序排序的优先队列，将greater改为less变为降序排序int i=0,n,a;cin >> n ;while(i<n){cin >> a ;x.push(a);i++;}llu s=0,y;i=0;while(i<n-1){y=x.top();x.pop();y+=x.top();x.pop();x.push(y);s+=y;i++;}cout << s << endl ;
}