Hust oj 2059 搬果子(优先队列）_综合

搬果子

Time Limit: 2000 MS

Memory Limit: 32768 K

Total Submit: 142(76 users)

Total Accepted: 72(65 users)

Rating:

Special Judge: No

Description

果园里面有n堆果子，每堆果子有xi个，每个果子的重量为1，小明每次把i,j两堆果子移成一堆，需要花费的体力为xi+xj。最后移成一堆，求最小花费体力值。
其中1<=n<=10000,1<=m<=10000。均为正整数。

Input

每组数据第一行输入一个正整数n，表示有n堆果子。

接下来一行有n个正整数，表示每堆果子的重量。

输入以EOF结尾。

Output

每组数据单独一行，输出所花费的最小体力值。

Sample Input

1 2 9

1 3 9 18 30

Sample Output

109

Hint

Source

HCPC2014校赛训练赛 3

Author

很显然的思路。每合拢一堆果子排一次序，不管sort或qsort肯定都会超时，所以用优先队列。模拟搬果子的过程就可以AC

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>using namespace std;int main()
{int n;int sum;int a[10005];while(~scanf("%d",&n)){int i,j,k,l,z;priority_queue<int, vector<int>, greater<int> > q;for (i=0;i<n;i++){scanf("%d",&j);q.push(j);}sum=0;while(q.size()>1){j=q.top();q.pop();z=q.top();q.pop();k=j+z;sum+=k;q.push(k);}printf("%d\n",sum);}
}