合并果子

题目 合并果子

思路分析

咋一看和前面的区间dp很像 但不一样的是 前面区间dp是只能选相邻的两堆进行合并

而这里 是可以选择任意两个进行合并的

那么 从贪心角度出发 每次选两个花费最小的进行合并呗

发现 这不就是哈夫曼树的构造方法吗

emmm 这类贪心就是经典的 Huffman Tree 的二叉堆模型

每次取出两个最小值 合并成一个 又放进去供选择

这个数据结构很容易可以想到用小根堆

代码实现

#include<bits/stdc++.h>

using namespace std;

priority_queue<int,vector<int>,greater<int>> heap;

int n;

int main()

{

    cin>>n;

    while(n--){

        int x;cin>>x;

        heap.push(x);

    }

    int res=0;

    while(heap.size()>1){

        int min1=heap.top();

        heap.pop();

        int min2=heap.top();

        heap.pop();

        int cost=min1+min2;

        res+=cost;

        heap.push(cost);

    }

    cout<<res;

    return 0;

}

同类题型

视频讲解

⬅️ k叉树 荷马史诗 🏠 00-刷题理模型 ➡️ 哈夫曼模型