泡泡合并

链接：https://ac.nowcoder.com/acm/contest/15932/B
来源：牛客网

题目描述

第一行输入一个整数T，代表本题有T组数据。(1 ≤ T ≤ 30)
对于每组输入：
第一行输入一个整数n，代表有n个气泡。(1 ≤ n ≤ 10000)
第二行输入n个整数aia_iai，代表每个泡泡的体积。(1 ≤aia_iai≤ 20000)

		

			对于每组数据，输出为一行。
		

		

			每行输出两个整数，并用空格表示。
		

		

			第一个整数代表小明将这些泡泡合并为一个所用的最小精力。
		

		

			第二个整数代表最终合并的这个泡泡的大小。
		

AC代码

http://ac.nowcoder.com/acm/contest/view-submission?submissionId=47797747

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
typedef long long ll;
int main()
{
    int T;
    scanf("%d", &T);
    while(T--)
    {
        int n;
        ll ans = 0;
        scanf("%d", &n);
        priority_queue<int, vector<int>, greater<int> > bub; //这里要注意加空格不然会变成移位操作
        int k = n;
        while(k--)
        {
            int x;
            scanf("%d", &x);
            bub.push(x);
        }
        while(bub.size() > 1)
        {
            int x, y;
            x = bub.top();
            bub.pop();
            y = bub.top();
            bub.pop();
            ans += x + y;
            bub.push(x + y - 1);
        }
        printf("%lld %lld\n",ans, bub.top());
        bub.pop();
    }
    return 0;
}

解题思路

要得到合成后最小的泡泡，当然是把n个泡泡的体积排序后从小到大两两合并，但是要注意每次合成后的泡泡可能比合成前原序列中第三小的泡泡的体积大，所以每次合并后都要再次对体积排序，题目n的范围最大是10000，所以暴力做至多要排序10000次，手写的快速排序试过了，会TLE，至于STL的sort还没试过,果断放弃了^_^.

这道题总结就是堆的模板题，或者说优先队列的语法题，思路并不太难想到，而关键是如何想到用堆的特性处理。

关于堆（也就是优先队列）可以百度：C++STL优先队列学习用法（比如大根堆，小根堆怎么定义，本质上堆就是一颗完全二叉树，越到树根相应的值就越大或越小，这里看不明白的话还是要学习一下用数组手写的堆），当然堆也有手写实现的版本，要比STL的优先队列更快。这里就先用STL优先队列足够了。

特别的，只有一个泡泡就不用合并，所花费的精力就是0。

然而，还有一个坑，你会发现最后输出要用%lld，这是因为泡泡的数量最多10000个，每个泡泡最大体积20000，这样最后的泡泡最大大约就是20000*10000=2e9,所以要用lld。

priority_queue

最后是STL.priority_queue基本操作：

.empty() 如果队列为空，则返回

.pop() 删除队顶元素，即删除第一个元素

.push() 加入一个元素

.size() 返回优先队列中拥有的元素个数

.top() 　返回优先队列对顶元素，返回优先队列中有最高优先级的元素

在默认的优先队列中，优先级高的先出队。在默认的int型中先出队的为较大的数。