贪心: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;
}
更多推荐
贪心:Huffman树
发布评论