优先队列的使用

windows live writer

终于安装好了windows live writer.(不知道什么问题一直出问题)。简直完美！

试一下的确很爽，先来一道优先队列压压惊！

题目描述

最近，Nova君遇到了一件非常棘手的问题。他需要整理非常多的解题报告。每份解题报告的题目数量是不定的。Nova君每次需要将两份报告的题目解析合成到一份里。假设两份报告的题解数分别为a和b，那么合成这两份报告消耗Nova君a+b的hp值。现在有n份报告，题解数分别为a0,a1,a2,,,an-1，请问Nova最少消耗多少hp？

输入

多组测试数据。每组数据，第一行为一个正整数n（INT范围内），代表报告份数，接下来一行，包含n个正整数（INT范围内）a0,a1,a2,,,an-1，代表每份报告的题解数。

输出

对于每组数据，输出一行，代表Nova需要付出的最少的hp值

输入样例

4
3 5 7 11

输出样例

49

Hint

陈题，然而请用优先队列实现

来源： <http://biancheng.love/contest/10/problem/A/index>
代码实现：

1 #include <bits/stdc++.h>
 2 #define max_size 1000010
 3 
 4 using namespace std;
 5 int a[max_size];
 6 
 7 struct cmp{
 8     bool operator()(int &a,int &b){
 9     return a>b;
10     }
11 };
12 
13 int main(){
14     priority_queue<int,vector<int>,cmp>q;
15     int n;
16     while(~scanf("%d",&n)){
17         long long ans=0;
18         int num;
19         for(int i=1;i<=n;i++){
20             scanf("%d",&num);
21             q.push(num);
22         }
23         int key,a,b;
24         while(!q.empty()){
25         a=q.top();
26         q.pop();
27         if(q.empty())break;
28         b=q.top();
29         q.pop();
30         ans+=a+b;
31         key=a+b;
32         q.push(key);
33         }
34         cout<<ans<<endl;
35     }
36 }

原文链接: https://www.cnblogs.com/zpfbuaa/p/4966857.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍