算法:贪心 + 优先队列
时间复杂度:$O(N \times log(N))$
经典贪心问题。
因在合并时尽量选取重量较小的果子以致合并的代价尽可能小,所以可采用小根堆,依次取堆顶的两个元素进行合并,再将合并后的元素插入至小根堆,直至小根堆仅有一个元素即已合成一堆。
注:小根堆已保证贪心的策略。
C++ 代码
#include <iostream>
#include <queue>
using namespace std;
int n, ans;
priority_queue <int, vector<int>, greater<int>> q; // 小根堆
int main()
{
cin >> n;
for (int i = 0; i < n; ++i) {
int x;
cin >> x;
q.push(x);
}
while (q.size() > 1) {
int a = q.top();
q.pop();
int b = q.top();
q.pop();
ans += a + b;
q.push(a + b);
}
cout << ans << endl;
return 0;
}