题目描述

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

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

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

对于任意的$1 \le i,j \le n$，$i \neq j$，都有：$s_i$不是$s_j$的前缀。

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

一个字符串被称为$k$进制字符串，当且仅当它的每个字符是$0$到$k-1$之间（包括$0$和$k-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)$。