题解2168 【荷马史诗】

· · 题解

思路

首先介绍一下哈夫曼树，哈夫曼树也叫最优二叉树，是一种带权路径（叶子节点权值乘该节点到根节点路径长度）之和最短的二叉树。通过哈夫曼树可以构造出哈夫曼编码，可以用于数据压缩和数据加密。

哈夫曼编码的原理是，利用哈夫曼树中权值越高（数据出现频率越高）的节点到根节点的距离越小（对应哈夫曼编码越短）的性质，将数据压缩成哈夫曼编码。正是由于每一个数据对应于树上的每一个叶子节点，而对应的编码为根到该叶子节点的路径，所以一串哈夫曼编码才能对应惟一的一串原码（即题目中所说si不是sj的前缀。），解码时才不会产生混淆。

依据题意和题目背景里面的一些暗示，思路可以明确，就是要求构造一个K进制的哈夫曼编码。平时我们所说的哈夫曼编码为2进制的，构造的方法也很容易（类似于NOIP2004 合并果子），本题也可以使用相同的思想。

首先明确需要维护什么。转换一下题意，不难知道我们需要维护的是最短的带权路径之和和该哈夫曼树的高度。然后便是如何维护，由于不需要知道哈夫曼树的具体形态，我们便可以按照哈夫曼树的构造方式，将当前最小的K个节点合并为1个父节点，直至只有一个父节点。看到“将最小K个节点合并”便可以明确使用优先队列（二叉堆）进行维护。

最后，我们需要注意一个细节。因为每次都是将k个节点合并为1个（减少k-1个），一共要将n个节点合并为1个，如果（n-1）%（k-1）！=0 则最后一次合并时不足k个。也就表明了最靠近根节点的位置反而没有被排满，因此我们需要加入k-1-（n-1）%（k-1）个空节点使每次合并都够k个节点（也就是利用空节点将其余的节点挤到更优的位置上）。

代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
#include <ext/pb_ds/priority_queue.hpp> //pb_ds库
#define LL long long 
using namespace std;
struct node{
    LL w,h;
    node(LL W, LL H){
        w=W,h=H;
    }
};
bool operator<(node a, node b){
    if(a.w!=b.w) return a.w>b.w; 
    return a.h>b.h;  //如果长度相等，高度小的优先
} //构造小根堆的操作。
__gnu_pbds::priority_queue <node, std::less<node>, __gnu_pbds::pairing_heap_tag> q; //优先队列
int n,k,cnt;
LL temp,maxh,ans;

int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1; i<=n; i++){
        scanf("%lld",&temp);
        q.push(node(temp,1));
    }
    if((n-1)%(k-1) != 0) cnt=k-1-(n-1)%(k-1);  //判断是否要补空节点
    for (int i=1; i<=cnt; i++)
        q.push(node(0,1)); //补空节点
    cnt+=n;     //cnt为根节点个数(最初每个根节点都为其本身）
    while(cnt>1){
        temp=maxh=0;
        for(int i=1; i<=k; i++){
            temp+=q.top().w;
            maxh=max(maxh,q.top().h);
            q.pop();
        }
        ans+=temp; //维护带权路径长度之和
        q.push(node(temp, maxh+1)); //合并，高度为最高子树高度+1
        cnt-=k-1; //减少根节点
    }
    printf("%lld\n%lld\n",ans,q.top().h-1);
    return 0;
}