【NC16663】合并果子

本文主要是介绍【NC16663】合并果子，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

合并果子

优先队列

思路

如果听说过“哈夫曼”这个词，那么此题的思路就很清晰了，有兴趣可以看看 $\lfloor$哈夫曼树$\rceil$。

由题意可知，要使体力的消耗最小，我们应该优先选择最小数量的果子进行合并，并不是排序之后按排序顺序依次合并，而是需要始终维护所有果子的数量最小值，这就不得不让人想起一个叫 “堆” 的数据结构，这种数据结构可以完美地适合这道题，具体见代码。

代码

#include <iostream>
#include <queue>
using namespace std;int main(void) {ios::sync_with_stdio(false);cin.tie(nullptr);int n = 0, a = 0, b = 0, ans = 0;cin >> n;// 将优先队列的排序方式定为从小到大priority_queue<int, vector<int>, greater<int>> pq;// 将输入的数据放入优先队列while (n--) {cin >> a;pq.emplace(a);}// 不停地取出堆顶的两个最小的数相加while (pq.size() > 1) {a = pq.top();pq.pop();b = pq.top();pq.pop();// 并累加结果ans += a + b;pq.emplace(a + b);}// 最后输出结果cout << ans << endl;return 0;
}

这篇关于【NC16663】合并果子的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---