BaiLian4080 Huffman编码树
解题思路
所求即为最短路径之和, 也等于新生成节点频率之和.所以可以使用优先队列每次获取一个最小值和次小值, 所求之和即为新生成节点的频率…再依次获取即可.
这个题还用到了priority_queue.使用如下:
Priority_queue:优先队列, 不仅可以存储数据还可以按照某种规则进行排序.每次的push, 和pop操作, 里面数据都会进行动态调整, 把优先级高的放在前面.
使用 :
template <class T, class Container = vector,
class Compare = less > class priority_queue;
T:数据类型, 第三个参数默认不写是从大到小, 如果从小到大可以使用greater.
代码
#include<iostream> #include<queue> using namespace std; priority_queue<int, vector<int>, greater<int> >Q; int total = 0; int main() { int n,w; cin >> n; while (n--) { cin >> w; Q.push(w); } while (Q.size() != 1) { int sum = 0; sum += Q.top(); Q.pop(); sum += Q.top(); Q.pop(); Q.push(sum); total += sum; } cout << total << endl; return 0; }
