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

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

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

    输入以EOF结尾。

3

1 2 9

5

1 3 9 18 30

15

109

BH

很显然的思路。每合拢一堆果子排一次序，不管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);}
}