Huffman

问题：构造一颗包含 \(n\) 个叶子节点的 \(k\) 叉树，第 \(i\) 个叶子节点深度 \(d_i,\) 权重\(w_i,\)使\(\sum\limits_{i=1}^nd_i*w_i\)最小
直观考虑：要使得权重大的在上面，权重小的在下面
因为对于一个叶子节点，他的贡献是他的权重*他到根的路径节点数，不妨使树转化为：
对每个叶子节点，使得他和根节点之间的所有节点（除去自己）都加上这个叶子结点的权重，就可以把贡献分摊到所有节点上
这样最终的总和就是所有节点的和
于是就有了一个贪心策略：
\(1.\) 建立小根堆，插入所有节点
\(2.\) 找到 \(k\) 个权重最小的节点，新加入一个节点，权重为他们之和
\(3.\) 重复 \(2\) 操作，直到堆的大小为 \(1\)

但是这个算法有一个\(bug:\)可能在深度为2时节点的数量已经不足\(k\)个
这样浪费了深度为\(2\)的空间，显然不是最小的构造

怎么解决？

肯定要使最底下一层的一些节点变成空，于是想到加入 \(0\) 元素，使得叶节点数 \(n\) 满足\((n-1)\%(k-1)=1\)

NOI2015 荷马史诗：

条件是没有一个字符串是另一个字符串的前缀，其实就是Huffman
最长\(s_i\)最短的限制？如果有两个相同的元素优先使用当前深度较小的元素

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std ;

typedef long long ll ;
const int N = 100100 ;

struct node {
	ll w ; int tim ;
};

bool operator <(node a, node b) {
	if (a.w != b.w) return a.w > b.w ;
	else return a.tim > b.tim ;
}

priority_queue <node> q ;
int n, k ;
ll ans ;
ll w[N] ;

int main() {
	scanf("%d%d", &n, &k) ;
	for (int i = 1; i <= n; i++) scanf("%lld", &w[i]) ;
	while ((n - 1) % (k - 1) != 0) w[++n] = 0 ;
	for (int i = 1; i <= n; i++) q.push((node){w[i], 0}) ;
	while (q.size() != 1) {
		int mxt = 0 ; ll sum = 0 ;
		for (int i = 1; i <= k; i++) {
			sum += q.top().w ; mxt = max(mxt, q.top().tim) ;
			q.pop() ;
		}
		q.push((node){sum, mxt + 1}) ;
		ans += sum ;
	}
	printf("%lld\n%d\n", ans, q.top().tim) ;
}