#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 类型的表示范围。
  • 贪心策略:哈夫曼树
    • 每次​选择最小的两堆合并​,可以保证总的合并代价最小。
    • 使用最小堆(优先队列) 维护果子的数量,每次取出最小的两堆进行合并,并将新堆放回堆中,直到只剩下一堆。

题目分析与解法

目标

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

思路

  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​。

结论

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