Huffman编码-荷马史诗 NOI2015 Day2

题目被吃了；Huffman编码的具体内容网上资料很多，所以被吃了。

建 Huffman 树方式如下：

将每个关键词的权值（这道题里就是这个词出现的次数）作为第一关键字，

其深度作为第二关键词，放入大根堆中，取堆顶前 k 个元素作为一个新的

节点的子节点。最终能合并为一棵树的条件是 (n-1) mod (k-1) = 0。

如果不满足，应该往堆里扔适量权值为 0 的“假节点”。

注意：

1.对于这道题，如果只将权值作第一关键字，只能得 55 分。一定要将深度作为第二关键词建堆！

2.关于最后文章的总长度，应该是每个节点的深度之和，但是并不需要枚举节点进行计算。

根据树上DP的思想，每次合并时将深度累加即可，代码中用 sum 实现了这一点。

 1 #include <stdio.h>
 2 #include <queue>
 3 
 4 using namespace std;
 5 
 6 typedef long long LL;
 7 
 8 struct node {
 9     LL v, deep;
10     node (LL v, LL deep):
11         v(v), deep(deep) { }
12 };
13 
14 bool operator < (const node& t1, const node& t2) { return t1.v > t2.v || t1.v == t2.v && t1.deep > t2.deep; }
15 
16 priority_queue<node> Q;
17 
18 LL n, k, ans;
19 
20 int main()
21 {
22     LL i, tmp;
23     scanf("%lld%lld", &n, &k);
24     if ((tmp = (n-1)%(k-1))) {
25         tmp = k-1-tmp;
26         while (tmp--) Q.push(node(0, 0));
27     }
28     for (i = 1; i <= n; ++i)
29         scanf("%lld", &tmp), Q.push(node(tmp, 0));
30     ans = 0;
31     while (Q.size() != 1) {
32         LL sum = 0, maxx = 0;
33         for (i = 1; i <= k; ++i)
34             sum += Q.top().v, maxx = max(maxx, Q.top().deep), Q.pop();
35         Q.push(node(sum, maxx+1));
36         ans += sum;
37     }
38     printf("%lld
%lld
", ans, Q.top().deep);
39     return 0;
40 }