A5703.简单的合并果子 题解 前言（废话） 好好好，又抄 NOIP 题是吧。 这个题我有两种解法 思路 挺像哈夫曼的。 方法 1 使用 STL 堆，每次弹出都会弹出两个最小的数，计算过后放回去即可。时间复杂度 O(nlog⁡n)O(n \log n)O(nlogn)。 方法 2 我们回归问题的本质，我们还是要选取最小的两堆果子，最清真、最自然的方式显然是排序了吧。先排序，选取最小的两堆果子，然后合并，插入。但是插入的效率太低了，我们想要优化。 我们可以把这些需要插入的点用一个队列存储起来，首先这些需要插入的点肯定会越来越大 显然 ， 这相当于延迟插入。当我们目标插入点就是我们当前最小的那一堆的时候，我们就把他插入进来。 以上是精神，代码写出来大概就是，桶排，建立两个队列，排序结果放进第一个当中，合并结果放在第二个当中，每次选从两个队列队头选取比较小的合并。 ——摘自洛谷《题解 P6038 【合并果子 加强版】》 时间复杂度 O(n)O(n)O(n)。 代码 方法 1 记住要设置，不要用初始的排序方法。 可以通过非常简单的 此题。 方法 2 同样使用 STL 堆。 可以通过数据量巨大的 此题。

因为数据范围比较小，方法就比较多了，直接不停排序也不会超时。如果范围较大，要考虑构建赫夫曼树了。

（远古代码，真正的pq不是这样的 时间复杂度：O(n2)O(n^2)O(n2)

#include <iostream> #include <queue> #include <vector> using namespace std; int main(){ int n,ans=0; priority_queue<int,vector<int>,greater<int>> q; cin >> n; for (int i=0;i<n;++i){ int t; cin >> t; q.push(t); } 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; }

这道题只需要把最小的两个果堆加起来就可以了，好多大佬都用的是优先队列，但由于本人太菜，只好用数组做。 如果这样想，那么每合并一次都需要排一次序，但事实上并不需要这么做（而且这样会超时，我之前用sort函数排就过了四个点，后面全都tle了），只需要给新合并的果堆找到所在的位置，并且将空的果堆删除就可以了。 下面AC代码。 > 双倍经验：题库合并果子

看了这道题解AC的人：114514，WA的：0.1919810 废话不多说，上代码：