Problem : Merge Fruits / 合并果子

---

任务总览表

任务名称	时间限制	内存限制	分数
合并果子	1 sec	1024 MB	10 points

---

题目描述

在一个果园里，多多已经将所有的果子打了下来，并按照不同种类的果子分成了不同的堆。多多决定把所有的果子合并成一堆。

每次合并时，多多可以选择任意两堆果子，将它们合并到一起，合并的代价等于这两堆果子的总重量。合并后的新堆可以继续参与后续的合并操作。

经过 n−1 次合并后，所有的果子会被合成一堆，而多多在整个过程中消耗的体力等于每次合并时的代价之和。

由于还需要搬运这些果子，多多希望通过​合理的合并顺序​，使得总的体力耗费最小。

---

输入格式

• 第一行包含一个整数 ​n​（1 ≤ n ≤ 30000），表示果子的种类数。
• 第二行包含 n 个整数，分别表示每种果子的数量。每种果子的数量为 ​a_i​（1 ≤ a_i ≤ 20000）。

---

输出格式

• 输出一个整数，即合并所有果子所需的最小体力消耗值。

---

样例输入和输出

输入样例 1

3
1 2 9

输出样例 1

15

输入样例 2

4
5 3 8 2

输出样例 2

34

---

提示

• 数据范围
  • n ≤ 30000，表示最多有 30000 种果子。
  • a_i ≤ 20000，每种果子的数量不会超过 ​20000​。
  • 最终的结果保证小于 2^31，即不会超过 int 类型的表示范围。
• 贪心策略：哈夫曼树
  • 每次​选择最小的两堆合并​，可以保证总的合并代价最小。
  • 使用最小堆（优先队列） 维护果子的数量，每次取出最小的两堆进行合并，并将新堆放回堆中，直到只剩下一堆。

---

题目分析与解法

目标

• 最优合并顺序 使得最终合并的总消耗最小。

思路

1. ​**使用最小堆（优先队列）**​：
   • 维护一个​最小堆​，每次取出最小的两堆合并，并将合并后的新堆加入到堆中。
   • 由于堆的操作（插入、删除最小值）​**时间复杂度为 O(log n)​，所以整体复杂度为 ​O(n log n)**​，适用于 n ≤ 30000 的情况。
2. 合并过程
   • 初始时，将所有果子数量放入最小堆。
   • 每次取出堆中最小的两堆合并，累加合并代价，并将新堆放入堆中。
   • 重复 直到所有果子合并成一堆。

---

时间复杂度分析

• ​建立最小堆​：O(n)
• ​每次合并操作​：
  • 取出两个最小值（O(log n)）
  • 插入新堆（O(log n)）
• ​共进行 n−1 次合并​，总的复杂度为 ​O(n log n)​，适用于 ​n ≤ 30000​。

---

结论

• 通过 最小堆 实现贪心策略，每次合并最小的两堆，最终可以得到​最优的最小体力消耗​。