蓝桥杯第1167题——荷马史诗

题目描述

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

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

对于任意的 1 ≤ i , j ≤ n ，i != j ，都有：si​ 不是 sj​ 的前缀。

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

一个字符串被称为 k 进制字符串，当且仅当它的每个字符是 0 到 k−1 之间（包括 0 和 k−1 ）的整数。

字符串 str1 被称为字符串 str2 的前缀，当且仅当：存在 1 ≤ t ≤ m ，使得 str1=str2[1..t]。其中，m 是字符串 str2 的长度，str2[1..t] 表示 str2 的前 t 个字符组成的字符串。

输入描述

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

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

其中， n ≤ 10^5 , k ≤ 9 , 0 < wi ​≤ 10^11。

输出描述

输出包括 2 行。

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

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

输入输出样例

示例 1

输入

4 2
1
1
2
2

输出

12
2

示例 2

输入

6 3
1
1
3
3
9
9

输出

36
3

解题思路 

题目的描述很长，解释的有点过于多，但其实如果你是计算机专业的学生，知道霍夫曼编码，题目的内容就不难理解了，反之则不然，我仅在此处简单的对霍夫曼编码的关键部分进行讲述，具体内容读者可以去搜索相关资料。

霍夫曼编码是一种文本压缩手段，通过没有序号指明的01串替换单词来压缩文章内容，用不同的01串来替换文章中的单词，为了让文章的解码结果唯一，代表不同单词的01串则互相不能是对方的前缀；而使文章具有唯一解的方法，就是利用一颗二叉树的叶子结点，对于一颗二叉树，向左走表示0，向右走表示1，每到一个叶子结点，其路径表示的01串就是一个单词，这种方式组成的n个叶子结点所表示的01串互相不会是别人的前缀；而为了让压缩后的01串总长度尽量短，出现频率越高的单词就越要放在二叉树的上层，这点很好理解。

题目的意思其实就是将二叉树升级为了k叉树，总体结构同霍夫曼编码，但同时也有很多细节需要各位同学把握和处理，综合下来并不容易。

具体的，我们需要将每个单词出现的次数进行排序，然后每次选取k个最小的数合成一个父节点，并将父节点重新放回这个序列，不断循环，因为需要放回再取，所以我们考虑使用优先队列。

编码思路

考虑题目要求我们最后要输出编码单词的最长长度，所以对于每个k叉树的结点我们都记录其次数和深度，初始深度我们均设置为0，而每次新加入的父节点所记录的深度，就是每次拿出的k个结点的最大深度再加上1。

在这个地方我们尤其需要关注到一个细节，对于二叉树而言我们每次一定会选取两个节点，所以不用担心这个问题。但对于k叉树，我们要尽量让叶子结点更靠近最终树的根结点，如果按照我们当前这样的设计由下至上的构建二叉树，就会让叶子结点聚到底端，使得每个单词所对应的k进制串都尽量的长，那么就违背题意和霍夫曼编码的初衷了。（根节点有位置当然是放在根节点所属的子节点位置更好）

对于上述讨论，我们参考以下输入，读者可以自行模拟两种方法所构建的3叉树的不同。

4 3
3
3
3
3

那么我们就要清楚地认识到，我们需要补充空节点，使得最后一次合并节点的时候利用满k个节点，于是我们想到对优先队列中补充数值为0的结点，具体补充多少呢？我们回忆一下刚才讨论的思路，我们每次都要取得k个节点合并成1个新节点放进去，那么我们每次都会消耗掉(k-1)个节点，而最终我们要求合并完后仅剩余一个最终根节点，那么就有如下式子：

n - (k - 1) - (k - 1) …… = 1

经过简单的变换我们便会得到规律：

n - 1 - (k - 1) - (k - 1) …… = 0

(n - 1) - (k - 1) - (k - 1) …… = 0

(n - 1) % (k - 1) = 0

所以只要n与k不满足上述式子，我们就将n进行自增，并添加一个数值为0的占位节点即可。

最后回归我们的所要求得的目标，也就是我们需要知道压缩后的文章长度为多少，此处给出结论，对每一个合并后的节点的值，也就是非叶子结点作相加便是答案。其实非常容易思考，随着k叉树不断地向上合并，叶子结点的值都会由于每一个新父节点的出现而被再次计算相加一次，并且与此同时其所对应的k进制串也增加了1位，那么加起来最终就是我们希望求得的ans，对此读者可以使用例子自行模拟。

具体代码

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception{
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        String[] temp = in.readLine().split(" ");
        int n = Integer.parseInt(temp[0]), k = Integer.parseInt(temp[1]);
        PriorityQueue<long[]> pq = new PriorityQueue<>(
            Comparator
                .comparing((long[] a) -> a[0])
                .thenComparing((long[] a) -> a[1])
        );
        for (int i = 0; i < n; i++) {
            temp = in.readLine().split(" ");
            long value = Long.parseLong(temp[0]);
            pq.offer(new long[]{value, 0});
        }
        while ((n - 1) % (k - 1) != 0) {
            pq.offer(new long[]{0, 0});
            n++;
        }
        long ans = 0;
        long x = 0;
        while (pq.size() != 1) {
            long s = 0;
            for (int i = 1; i <= k; i++) {
                long[] p = pq.poll();
                s += p[0];
                x = Math.max(x, p[1]);
            }
            ans += s;
            pq.offer(new long[]{s, x + 1});
        }
        System.out.println(ans);
        System.out.println(pq.poll()[1]);
    }
}