贪心-哈夫曼树——acwing

题目：合并果子

148. 合并果子 - AcWing题库

分析

典型的哈夫曼树。也是最优二叉树，是一类带权路径长度最短的树。每次取两个最小的，合并成新的。

其实就是贪心，因为合并次数是固定的，每次都取最小能保证答案最小。

思考存储结构就是 能让最小的在前面就行，可以小根堆，也可以multiset

代码 1(multiset容器）

用multiset容器来存储数据，自动排序，目的是为了让最小的在最前面。

#include<bits/stdc++.h>
using namespace std;

multiset<int> s;

int main() {
    int n;
    cin >> n;
    for(int i = 0; i < n; i ++) {
        int x; cin >> x;
        s.insert(x);
    }
    int res = 0;
    for(int i = 0; i < n-1; i ++) {
        set<int>::iterator it;
        it = s.begin();
        int a = *it; s.erase(s.begin());
        it = s.begin();
        int b = *it; s.erase(s.begin());
        res += (a+b);
        s.insert(a+b);
    }
    cout << res << endl;
    return 0;
}

 代码2（小根堆）

取最值问题可以用到小根堆或者大根堆

#include<bits/stdc++.h>
using namespace std;

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

int main() {
    int n;
    cin >> n;
    for(int i = 0; i < n; i ++) {
        int x; cin >> x;
        h.push(x);
    }
    
    int res = 0;
    while(h.size()>1) {
        auto a = h.top(); h.pop();
        auto b = h.top(); h.pop();
        res += (a+b);
        h.push(a+b);
    }
    cout << res << endl;
    return 0;
}