分析

  • 这是要维护一个k叉哈夫曼树。有几个值得注意的地方：补零 合并

  • 合并：
    每次合并k个节点，其实每多k-1个节点,那么就要和原本的节点产生一个新节点，如果这是个满k叉树，那么最后的的总

节点个数就是(c+1)*(k-1)+1(c为一个常数),将其设为n,那么判定他为一棵满k叉树就是判断(n-1)%(k-1)是否为0。每次合

并挑最小的k个合并,为什么？我不知道这个贪心是否正确，以二叉树为例，假设当前有a,b,c(a>b>c),如果把a,b合并为d，

c与d合并，代价是w1=hc+d(c+1),如果把b,c合并为e，a与e合并，代价是w2=ha+(h+1)e，两者相减，w2<w1,小的先合

并最优

  • 补零：为什么需要补0呢，口胡一下。假设这不是一棵满k叉树，那么必然有一些节点空缺，如果当前我们合并成下面这个样子
    图片说明

然后继续合并图片说明

（虚线表示不存在的节点和边）我们不是要求满的k叉树吗？为什么6的节点只有两个？可以发现，如果我们把1,2,3节点

任意一个移至节点7，得到的结果是有可能小于当前求出的结果的，所以这不是最优解。

这就是补零的意义。至于补多少零，因为满k叉树共有(k-1)*(c+1)+1个点,所以还要多加k-1-(n-1)%(k-1)个0

后话

  • 很感谢rain姐姐的思路，但由于tcl还是去看了题解，却又一知半解。写出来清晰多了，Thanks♪(･ω･)ﾉ