[NOI 2015] 荷马史诗：贪心 Huffman编码

题意：给出n个单词出现的频率，用k进制字符串给它们编码，使得编码没有一个是另一个的前缀，且替换后文本总长最小，在此前提下最长编码最短。输出总长和最长编码的长度。（2≤n≤10^5，2≤k≤9） 可以把所有编码放在Trie树上，只有叶子结点是终止结点。如果能构成满k叉树，显然最优解是满k叉树。否则，最优解中空结点是最深的叶子的兄弟。

为了统一两种情况，把Trie树采用加虚点的方式补成满k叉树。一棵满k叉树总能以这种方式构造：从只有一个结点的树开始，每次给一个叶子结点添加k个儿子——净增加(k-1)个叶子。于是，满k叉树的叶子数=1+(k-1)m，m为自然数。不要补多了。一开始我想错了，补成完全k叉树......

文本总长=。换个方式计算，设，当u是叶子，，那么文本总长=。上一段描述的满k叉树构造方式是自顶向下的，也可以自底向上构造：从所有叶子开始，每次取k棵子树合并成一棵树，再把这棵树作为子树，重复合并，直至只剩下一个结点。定义一次合并的代价为新树根结点的w，则文本总长=合并总代价。任取k棵子树合并这个过程都可以进行。如果取w最小的的k棵子树合并，那么本次代价最小，为以后的合并提供的新树的w也最小，因而这样构造的编码树文本总长最小。这就是Huffman编码。用小根堆实现。

本题还要求在文本总长最小的前提下最长编码最短。显然，w相等时，优先选取高度小的树即可。

重复造了个轮子......typedef pair<ull, int> Node就好了嘛。

#include <cstdio>
#include <queue>
#include <functional>
#include <vector>
using namespace std;
typedef unsigned long long ull;
const int MAX_K = 9;
struct Node {
	ull w;
	int h;
	bool operator>(const Node& rhs) const
	{
		return w > rhs.w || (w == rhs.w && h > rhs.h);
	}
};
priority_queue<Node, vector<Node>, greater<Node> > Q;

Node v[MAX_K];

int main()
{
	int n, k;
	scanf("%d %d", &n, &k);
	for (int i = 0; i < n; ++i) {
		ull x;
		scanf("%llu", &x);
		Q.push((Node){x, 0});
	}
	int m = (n+k-3)/(k-1)*(k-1)+1;
	for (int i = n; i < m; ++i)
		Q.push((Node){0, 0});
	ull sum = 0;
	while (Q.size() > 1) {
		ull w = 0;
		int h = 0;
		for (int i = 0; i < k; ++i) {
			v[i] = Q.top();
			Q.pop();
			w += v[i].w;
			h = max(h, v[i].h+1);
		}
		Q.push((Node){w, h});
		sum += w;
	}
	printf("%llu\n%d\n", sum, Q.top().h);
	return 0;
}