P2-2017级算法第二次上机 B 女娲加农炮

题目描述

（请不要带着科学的视角去看待题干故事，因为这本来就是以游戏为背景的）

女娲加农炮是中国阵营的专属T3战车单位。这种装备了250mm口径核裂变重磅炮的钢铁巨兽是一种极为恐怖的屠戮机器，常常被安置在中国大批机械化部队的最前端，形成一堵坚不可摧、势不可挡的钢铁长城。

表面上女娲加农炮是由东北重工集团研制而成，但事实上，东北重工只进行了方案论证和实车建造，女娲加农炮真正的缔造者，是来自中国的天才科学家芸如。

现在芸如想化核裂变为核聚变，从而让女娲加农炮的火力再上一层楼。已知有N种不同的原子核（这里请忽略自然界原子核的种类上限），第i种原子核的重量为a[i]。

将两种原子核聚合在一起，消耗的能量等于两种原子核的重量之和。在经过n-1次聚合之后，聚合完成。芸如想使整个聚合过程消耗的能量最小，请求出这个最小的能量值。

输入

多组数据输入，第一个数为原子核的种类N。（N<=1e6）

接下来N个整数，代表N种原子核的重量。（在int范围内并用空格隔开）

输出

对于每组数据，输出一行，为聚合过程能量消耗的最小值。（保证结果在int范围内）

输入样例

4

1 2 3 4

输出样例

19

思路

利用优先队列，每次将最小的两个从优先队列中取出并加和，然后将加和之后的元素重新放回优先队列并维护即可。最后输出累加值即为所求。

参考代码

#include<iostream>  
#include<cstdio>  
#include<algorithm>  
#include<queue>  
using namespace std;  
priority_queue<int,vector<int>,greater<int> >q;  
int main()  
{  
    int N;  
    while(scanf("%d",&N) == 1){  
        //优先队列  
        while(!q.empty())  
            q.pop();  
        int res = 0,weight;  
        for(int i = 0;i < N;i++){  
             scanf("%d",&weight);  
             q.push(weight);  
        }  
        for(int i = 1;i < N;i++){  
            int first = q.top();  
            q.pop();  
            int second = q.top();  
            q.pop();  
            q.push(first+second);  
            res += first + second;  
        }  
        printf("%d\n",res);  
    }  
}