AcWing 148. 合并果子

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 148. 合并果子原题链接简单

作者：

yxc , 2019-07-30 17:17:36 , 所有人可见 , 阅读 19525

128

40

算法

(贪心,哈夫曼树,堆,优先队列) $O(nlogn)$

经典哈夫曼树的模型，每次合并重量最小的两堆果子即可。

时间复杂度

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

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

C++ 代码

#include <iostream>
#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)
    {
        int a = heap.top(); heap.pop();
        int b = heap.top(); heap.pop();
        res += a + b;
        heap.push(a + b);
    }

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

26 评论

virtualbool 2023-08-08 17:48

我还没听讲解，竟然和y总写的一模一样，好开心

在下令狐冲 9个月前

👍

Mathemartist. 7个月前

牛啊牛啊

奋伟 2023-03-08 21:15

wocao

快速冥 9个月前

最简单的一集

LZZZXC 2021-02-09 18:28

直接用优先队列的话能不能过呢

Anoxia_3 2021-02-13 14:28

可以的，直接取负就可以了。

#include <iostream>
#include <queue>

using namespace std;

int main()
{
    int n;
    cin >> n;
    priority_queue<int> heap;
    while(n--)
    {
        int x;
        cin >> x;
        heap.push(-x);
    }

    int ans = 0;
    while(heap.size() > 1)
    {
        int a = heap.top();
        heap.pop();
        int b = heap.top();
        heap.pop();

        ans -= a + b;
        heap.push(a + b);
    }

    cout << ans << endl;
}