贪心：Huffman树

贪心：Huffman树"/>

贪心：Huffman树

 合并果子：

该题与石子合并的区别：石子合并是两两相邻才能合并，这题是任意两点合并

该题的思路：每次合并最小的两个点

#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;
}