#P342. Merge Fruits / 合并果子
Merge Fruits / 合并果子
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 类型的表示范围。
- 贪心策略:哈夫曼树
- 每次选择最小的两堆合并,可以保证总的合并代价最小。
- 使用最小堆(优先队列) 维护果子的数量,每次取出最小的两堆进行合并,并将新堆放回堆中,直到只剩下一堆。
题目分析与解法
目标
- 最优合并顺序 使得最终合并的总消耗最小。
思路
- **使用最小堆(优先队列)**:
- 维护一个最小堆,每次取出最小的两堆合并,并将合并后的新堆加入到堆中。
- 由于堆的操作(插入、删除最小值)**时间复杂度为 O(log n),所以整体复杂度为 O(n log n)**,适用于 n ≤ 30000 的情况。
- 合并过程
- 初始时,将所有果子数量放入最小堆。
- 每次取出堆中最小的两堆合并,累加合并代价,并将新堆放入堆中。
- 重复 直到所有果子合并成一堆。
时间复杂度分析
- 建立最小堆:O(n)
- 每次合并操作:
- 取出两个最小值(O(log n))
- 插入新堆(O(log n))
- 共进行 n−1 次合并,总的复杂度为 O(n log n),适用于 n ≤ 30000。
结论
- 通过 最小堆 实现贪心策略,每次合并最小的两堆,最终可以得到最优的最小体力消耗。