AcWing 148. 合并果子
原题链接
简单
作者:
我要出去乱说
,
2021-01-31 21:06:40
,
所有人可见
,
阅读 284
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
int main()
{
int n;
cin >> n;
priority_queue<int, vector<int>, greater<int>> heap; //小根堆
while (n -- )
{
int x;
cin >> x;
heap.push(x);
}
int res = 0;
while (heap.size() > 1) //最少要两个元素才能继续合并
{
int a = heap.top(); heap.pop(); //小根堆最小的两个元素合并
int b = heap.top(); heap.pop();
res += a + b;
heap.push(a + b); //合并后的新堆再加入
}
cout << res << endl;
return 0;
}