思路:每次合并两堆最小的果子,所消耗的体力最少,每次取最小值的话用小根堆会很方便。
#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 i = heap.top(); heap.pop(); //取最小的两堆果子
int j = heap.top(); heap.pop();
res += i + j; //res累加体力消耗
heap.push(i + j); //两堆小果子合并成一堆果子,再放入小根堆
}
cout << res << endl;
return 0;
}