AC. 梦想

frank_c1

[NOI 2015] 荷马史诗

发布于2016年05月12日 | 暂无评论 | 572阅读 | 贪心

题目描述

追逐影子的人,自己就是影子。 ——荷马

Allison 最近迷上了文学。她喜欢在一个慵懒的午后,细细地品上一杯卡布奇诺,静静地阅读她爱不释手的《荷马史诗》。但是由《奥德赛》和《伊利亚特》组成的鸿篇巨制《荷马史诗》实在是太长了,Allison 想通过一种编码方式使得它变得短一些。

一部《荷马史诗》中有n种不同的单词,从1n进行编号。其中第i种单词出现的总次数为w_i。Allison 想要用k进制串s_i来替换第i种单词,使得其满足如下要求:

对于任意的1 \le i,j \le ni \neq j,都有:s_i不是s_j的前缀。

现在 Allison 想要知道,如何选择s_i,才能使替换以后得到的新的《荷马史诗》长度最小。在确保总长度最小的情况下,Allison 还想知道最长的s_i的最短长度是多少?

一个字符串被称为k进制字符串,当且仅当它的每个字符是0k-1之间(包括0k-1)的整数。

字符串Str1被称为字符串Str2的前缀,当且仅当:存在1 \le t \le m,使得Str1=Str2[1..t]。其中,m是字符串Str2的长度,Str2[1..t] 表示Str2的前t个字符组成的字符串。

输入格式

输入文件的第1行包含2个正整数n,k,中间用单个空格隔开,表示共有n种单词,需要使用k进制字符串进行替换。

接下来n行,第i+1行包含1个非负整数w_i,表示第i种单词的出现次数。

2 \le n \le 100000,2 \le k \le 9

输出格式

输出文件包括 2 行。

1行输出1个整数,为《荷马史诗》经过重新编码以后的最短长度。

2行输出1个整数,为保证最短总长度的情况下,最长字符串s_i的最短长度。

题目解析

NOI的难度真是越来越接近NOIP了。

观察题目性质,与Huffman树的构造方式非常相似。这启发我们借鉴Huffman树的思想来解决本题。

首先解决第一个子问题。若(n-1) \mod (k-1) = 0,那就和普通的Huffman树构造基本一样,即每次选取权值最小的k棵子树,新建一个结点x作为它们在树上的父亲,并将x的权值赋为这k棵子树的和。若(n-1) \mod (k-1) \neq 0,也比较容易解决,我们要保证权值大的深度尽量小,那就先选取(n-1) \mod (k-1) +1个权值最小的结点,就将问题转化成上面一种情况了。

再来考虑第二个子问题。如何保证串长最短?也就是保证Huffman树的高度最小。我们在选取权值最小的k个结点时,相同权值的情况下应贪心地选取子树高度最大的。这样就可以满足第二个子问题的要求了。

总时间复杂度O(n \log n)