题目：合并果子
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;
}
