洛谷 P2168 [NOI2015]荷马史诗 题解【哈夫曼树】【贪心】

点击量：134

    哈夫曼树+一点点贪心技巧。

目录

题目描述

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

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

 

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

 

对于任意的\(1\le i,j\le n,i\not= 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\)行。

 

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

 

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

 

输入输出样例

输入样例#1：

4 2
1
1
2
2

输出样例#1：

12
2

输入样例#2：

6 3
1
1
3
3
9
9

输出样例#2：

36
3

说明

【样例说明 1】

用\(X_{(k)}\)表示\(X\)是以\(k\)进制表示的字符串。

 

一种最优方案：令\(00){(2)}\)替换第\(1\)种单词，\(01_{(2)}\)替换第\(2\)种单词，\(10_{(2)}\) 替换第\(3\)种单词，\(11_{(2)}\)替换第\(4\)种单词。在这种方案下，编码以后的最短长度为：$$1\times 2+1\times 2+2\times 2+2\times 2 = 12$$

最长字符串\(s_i\)的长度为\(2\)。

 

一种非最优方案：令 \(000_{(2)}\)替换第\(1\)种单词，\(001_{(2)}\)替换第\(2\)种单词，\(01_{(2)}\)替换第\(3\)种单词，\(1_{(2)}\)替换第\(4\)种单词。在这种方案下，编码以后的最短长度为：$$1\times 3+1\times 3+2\times 2+2\times 1 = 12$$

最长字符串\(s_i\)的长度为\(3\)。与最优方案相比，文章的长度相同，但是最长字符串的长度更长一些。

 

【样例说明 2】

一种最优方案：令\(000(3)\)替换第\(1\)种单词，\(001_{(3)}\)替换第\(2\)种单词，\(01_{(3)}\)替换第\(3\)种单词，\(02_{(3)}\)替换第\(4\)种单词，\(1_{(3)}\)替换第\(5\)种单词，\(2_{(3)}\)替换第\(6\)种单词。

【数据规模与约定】

所有测试数据的范围和特点如下表所示

【提示】

选手请注意使用64位整数进行输入输出、存储和计算。

 

【评分方式】
对于每个测试点：

 

若输出文件的第\(1\)行正确，得到该测试点\(40\%\)的分数；

若输出文件完全正确，得到该测试点\(100\%\)的分数。

题解：

    这个题是哈夫曼树的基础题。哈夫曼编码就表示没有任何一个编码是另一个编码的前缀。也就是在一棵多叉树上，只有叶子节点代表一个编码的结尾。这样可以让定长的编码变为不定长，令出现次数多的编码较短，从而缩短所有编码的总长。但是和这个题有什么关系呢？

    合并果子这道题的堆解法其实就是在构造哈夫曼二叉树。一开始每一堆果子都是叶子节点，在合并过程中形成森林，最后合成一棵树。每个节点到根的距离和就是答案，而哈夫曼树可以保证这个值最小。

    哈夫曼树其实就是在让出现次数多的叶子节点的深度尽可能浅，在合并果子一题里就是果子的数量，而在这个题里是字符串出现的次数。两棵树合并的意义就是让两棵树的前缀相同，我们知道这是个子问题，在已经合并好了的节点已经满足了没有一个点的编码是另一个点编码的后缀，因此让它们添上同样的前缀也不会影响。这样我们用类似合并果子的方法做，就能拿到\(40\%\)的分数。

    而我们要在保证第一问的前提下完成第二问，那么就要考虑在堆中添加第二关键字。这里的第二关键字是什么呢？根据题目意义，编码的长度就是深度，我们只要在权值(已经对答案做出的贡献)相同的元素中优先选择深度浅的，就能保证答案最优且深度总是最浅。因为我们合并的层次是从下到上的。

    不过要注意一点，哈夫曼树是一棵满树。什么意思呢？如果它是一棵\(k\)叉树，那么它的所有节点要么有\(k\)个节点，要么是叶子节点。但是如果\((k-1)\not| (n-1)\)怎么办呢？

    首先来解释一下为什么要\((k-1)|(n-1)\)。每次合并减少了\(k-1\)个连通块（树或者点），一共要减少\(n-1\)个。但是如果原来不能整除，就要尽可能让节点的深度变浅，但是因为这个浅没有标准，所以我们就要差多少补多少，就当多了差值大小个权值为\(0\)的节点。因为它们在小根堆顶，所以它们会被放在哈夫曼树最深的位置。这样一来贪心就没有问题了。

Code：

#include<cstdio>
#include<queue>
struct node
{
    int d;
    long long v;
    node(int d,long long v)
    {
        this->d=d;
        this->v=v;
    }
    node(){}
    friend bool operator <(node a,node b)//两个关键字
    {
        return a.v!=b.v?a.v>b.v:a.d>b.d;
    }
};
std::priority_queue<node> q;
int main()
{
    int n,k;
    long long u;
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;++i)
    {
        scanf("%lld",&u);
        q.push(node(0,u));
    }
    while((n-1)%(k-1))//用权值为0的节点补
    {
        q.push(node(0,0));
        ++n;
    }
    long long sum=0;
    while(q.size()>1)
    {
        long long tmp=0,maxd=0;
        for(int i=1;i<=k;++i)//每次取出k个，放回1个
        {
            node x=q.top();
            q.pop();
            maxd=maxd>x.d?maxd:x.d;
            tmp+=x.v;
        }
        sum+=tmp;
        q.push(node(maxd+1,tmp));
    }
    printf("%lld\n%d",sum,q.top().d);
    return 0;
}