AcWing 148. 合并果子

小白

2022-08-03

算法 AcWing

题目

在一个果园里，达达已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。
达达决定把所有的果子合成一堆。
每一次合并，达达可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。
可以看出，所有的果子经过 $n−1$ 次合并之后，就只剩下一堆了。
达达在合并果子时总共消耗的体力等于每次合并所耗体力之和。
因为还要花大力气把这些果子搬回家，所以达达在合并果子时要尽可能地节省体力。
假定每个果子重量都为 $1$ ，并且已知果子的种类数和每种果子的数目，你的任务是设计出合并的次序方案，使达达耗费的体力最少，并输出这个最小的体力耗费值。
例如有 $3$ 种果子，数目依次为 $1$ ， $2$ ， $9$ 。
可以先将 $1$ 、 $2$ 堆合并，新堆数目为 $3$ ，耗费体力为 $3$ 。
接着，将新堆与原先的第三堆合并，又得到新的堆，数目为 $12$ ，耗费体力为 $12$ 。
所以达达总共耗费体力= $3+12=15$ 。
可以证明 $15$ 为最小的体力耗费值。

输入格式
输入包括两行，第一行是一个整数 $n$ ，表示果子的种类数。
第二行包含 $n$ 个整数，用空格分隔，第 $i$ 个整数 $a_i$ 是第 $i$ 种果子的数目。

输出格式
输出包括一行，这一行只包含一个整数，也就是最小的体力耗费值。
输入数据保证这个值小于 $2^{31}$ 。

数据范围
$1≤n≤10000$ ,
$1≤a_i≤20000$

输入样例：

3 
1 2 9

输出样例：

思路

模拟

对于给定的数据，我们进行模拟，如果第一次合并 1 + 2 = 3 ，第二次合并 3 + 9 = 12 ，消耗的总体力值是 1 + 2 + 1 + 2 + 9 = 15
我们换一种合并方式：第一次合并 1 + 9 = 10 ，第二次合并 10 + 2 = 12 ，消耗的总体力值是 1 + 9 +1 + 9 + 2 = 22
继续换一种方式：第一次合并 2 + 9 = 11 ，第二次合并 11 +1 = 12 ，消耗的总体力值是 2 + 9 + 2 + 9 +1 = 23
观察发现，每次越早合并的数，对最后的影响就会越多，第一种合并1、2 用到2次，而9用到一次，第二种合并，1、9用到两次，2用到一次，所以我们想要最后的结果最小，那么就要使值较大的数加的次数最少，值小的数加的次数多
我们就可以将所有的数加入到小根堆（优先队列）中，每次合并最小的两个，然后将和放入队列中，进行下一轮循环，直到最后队列中仅剩一个数

算法
(贪心,哈夫曼树,堆,优先队列) $O(n\log n)$
经典哈夫曼树的模型，每次合并重量最小的两堆果子即可。

时间复杂度
使用小根堆维护所有果子，每次弹出堆顶的两堆果子，并将其合并，合并之后将两堆重量之和再次插入小根堆中。

每次操作会将果子的堆数减一，一共操作 $n−1$ 次即可将所有果子合并成1堆。每次操作涉及到2次堆的删除操作和1次堆的插入操作，计算量是 $O(\log n)$ 。因此总时间复杂度是 $O(n\log n)$ 。

题解

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

int main()
{
    int n;
    scanf("%d", &n);
    priority_queue<int, vector<int>, greater<int>> heap;
    while (n -- )
    {
        int x;
        scanf("%d", &x);
        heap.push(x);
    }

    int res = 0;
    while (heap.size() > 1)
    {
        auto a = heap.top(); heap.pop();
        auto b = heap.top(); heap.pop();
        res += a + b;
        heap.push(a + b);
    }

    printf("%d\n", res);
    return 0;
}