- 难度：中等
- 标签：贪心、优先队列
题目
给出 n 个数，现在要将这 n 个数合并成一个数，每次只能选择两个数 a, b 合并，每次合并需要消耗 a+b 的能量，输出将这 n 个数合并成一个数后消耗的最小能量。
注意事项
2 ≤ n ≤ 50000，合并后的数字不会超过 int 范围
样例
Sample Input:
[1, 2, 3, 4]
Sample Output:
19
Sample Input:
[2, 8, 4, 1]
Sample Output:
25
解答
本题为优先队列的简单应用，代码如下：
class Solution {
public:
/**
* @param numbers: the numbers
* @return : the minimum cost
*/
int mergeNumber(vector<int> &numbers)
{
// 创建一个小顶堆 heap
priority_queue<int, vector<int>, greater<int>> heap;
int a, b, val, sum = 0;
for(auto x : numbers)
heap.push(x);
while(heap.size() != 1)
{
a = heap.top();
heap.pop();
b = heap.top();
heap.pop();
val = a + b;
heap.push(val);
sum += val;
}
return sum;
}
};
