AcWing 149 荷马史诗(Huffman树)
2020-12-26 15:28
标签：出现 后缀 scan code fir 代码 tps 有一个 一个 题目链接 ??将所有的字符串编码看成是一棵trie，因为所有的字符串都不互为前后缀，所以每一个字符串都末尾都位于trie的叶子结点上。 ,greater > pq;
for (int i = 0; i AcWing 149 荷马史诗(Huffman树) 标签：出现 后缀 scan code fir 代码 tps 有一个 一个 原文地址：https://www.cnblogs.com/shuitiangong/p/13369673.html解题思路
??因为要确保总长度最小，所以对于出现次数越多的字符串，其叶子在trie上的深度就越浅，那么出现次数越少的字符显然其叶子深度也就越深。所以可以用出现次数做权值，用优先队列来合并叶子结点并生成父节点。并且为了保证权值大的点尽量靠近根，我们用权值为0的点对叶子做填充，使整个树为一个满k叉树。
??最后还有一个问题，如何确保最长的字符串编码最短。举个例子，k=3的时候有3个权值为2个结点，1个深度为3，另外两个深度为0，那么让两个深度为0的结点结合，更有希望让整个树的树高更低。即对于权值相同的点优先合并深度最浅的。代码
const int maxn = 1e4+10;
int n,k; P t[20];
int main(){
scanf("%d%d",&n,&k);
priority_queue
文章标题：AcWing 149 荷马史诗(Huffman树)
文章链接：http://soscw.com/index.php/essay/38382.html