【BZOJ4198】【NOI2015】荷马史诗 K叉哈夫曼树

感觉以前就做过这道题,不过题面不太一样,去翻了翻OJ记录,也没有A过,所以今天重写了一下。

题目链接

算法和普通的哈夫曼树差别不大,只是从取堆顶两个变成取堆顶k个。

但是这可能会出现问题,因为如果最终构出的树如果不是满的那么出现次数最多的几个节点很有可能不满的占据一个子树,而深度却并不大,这就会导致深度小的节点被浪费掉,因为将深度大的任何叶子节点拿来填补上都不会使答案更差。

解决的办法是加入虚点。也就是加入尽可能少的权值为0的节点,使得不存在任何一个非叶子结点有少于K个儿子。

根据K叉树的性质,我们可以得到,要得到这棵树需要合并(n-1)/(k-1)次(合并一次就会让节点总数减少k-1个,最后剩一个节点)如果不能整除,就不能满足贪心的原理。于是我们将缺少的部分补上,也就是说,如果(n-1)%(k-1)=r!=0,就加入k-1-r个权值为0的节点做k叉哈夫曼树。

注意一定要特判(n-1)%(k-1)=r!=0,否则就不要加入节点。(我就是在这里WA*1)

还有,要开LL(WA*2)

至于第二问在满足第一问的情况下求最大长度最小,只需要在堆里加入双关键字排序,第二关键字设定为这个节点团中最大的深度。节点团权值相同时,深度小的优先合并。

统计答案的时候,每合并一次就给ans增加上合并后的节点团大小,最小深度只要输出最终节点团的最大深度即可。

然后下面就是代码啦~

 

不如来评论一发?