在一个果园里多多已经将所有的果子打了下来而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。 每一次合并多多可以把两堆果子合并到一起消耗的体力等于两堆果子的重量之和。可以看出所有的果子经过 n−1次合并之后 就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。 因为还要花大力气把这些果子搬回家所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为 1 并

算法1

(贪心+优先队列) $O(nlogn)$

首先，根据哈夫曼编码的思想，我们应该优先选择小堆进行合并，因为合并后的堆的大小更大，可以使得之后的合并操作中所需要的体力更少。

因此，我们可以使用一个小根堆来维护所有的果堆，每次取出两个最小的堆进行合并，并将合并后的堆重新放回小根堆中。由于每次合并都是选择最小的两个堆进行，因此可以保证最终的合并顺序一定是最优的。

时间复杂度

对于每个果堆，都需要进行一次插入操作，共需要插入n个堆，因此插入的总时间复杂度为$O(nlogn)$。每次合并操作需要取出两个堆，因此需要进行n-1次合并，每次合并需要取出两个堆，再将合并后的堆插入优先队列中，因此每次合并的时间复杂度为$O(logn)$。因此，总时间复杂度为$O(nlogn)$。

C++ 代码

算法2

(贪心+线段树) $O(nlogn)$

我们可以将当前所有堆的大小看做线段树上的节点，线段树上每个节点维护的信息为该节点所表示的区间内所有堆的大小之和。初始时，每个叶子节点的值即为对应果堆的大小。

接下来，我们每次需要找到当前最小的两堆进行合并，那么这两堆对应的线段树上的节点，应该分别是区间最小值和次小值对应的节点。找到这两个节点后，将它们的值相加，并将新的值赋给区间最小值对应的节点，然后将次小值对应的节点标记为无效节点。这样，我们就完成了一次合并操作，并且在合并过程中，只需要修改线段树上最多4个节点的值。

最终，所有果堆都合并到了一起，我们只需要求出线段树的根节点的值，即为最小的体力耗费值。

时间复杂度

线段树上每个节点最多被修改一次，因此总时间复杂度为$O(nlogn)$。

C++ 代码