Luogu P2168 [NOI2015]荷马史诗

题目
哈夫曼树的每个叶子结点都有一个权值（表示某数据的出现频率），且\(\sum dis_ival_i\)最小。
哈夫曼树中，权值和越大的集合离根节点越近。
而每个数据对应从根节点到该叶子结点的一种编码，显然这些编码没有相互的前缀和后缀关系。
对于文章压缩而言，叶子节点的权值就是某单词的出现次数，该节点到叶子结点的路径就是该叶子节点的单词压缩后的形态。
哈夫曼树的每个非叶子节点最多有\(k\)个儿子，在文章压缩中这个\(k\)就是字符集大小。
构建哈夫曼树的方法是每次选出未被选过的权值最小的\(k\)个点，这\(k\)个点的父亲的权值为这\(k\)个点的权值和。
这个构建方法显然可以用一个堆来做。
然后我们考虑怎么做这道题。
我们需要把节点个数补到\(k-1\)的倍数，来保证最后只有一个未被标记的点即根节点。
然后我们直接做就完事了。
最终的文章长度为\(\sum dis_ival_i\)，也就是除根节点以外所有点的权值。
而最长字符串的长度就是最大节点深度-1。

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=100007;
int n,k;
struct node{LL w;int h;};
int operator<(node a,node b){return a.w>b.w||(a.w==b.w&&a.h>b.h);}
priority_queue<node>q;
LL read(){LL x=0;char c=getchar();while(!isdigit(c))c=getchar();while(isdigit(c))x=x*10+c-48,c=getchar();return x;}
int main()
{
    n=read(),k=read();int i,d;LL s,ans=0;
    for(i=1;i<=n;++i) q.push((node){read(),1});
    while((n-1)%(k-1)) q.push((node){0,1}),++n;
    while(n^1)
    {
    s=d=0;
    for(i=1;i<=k;++i) s+=q.top().w,d=max(d,q.top().h),q.pop();
    ans+=s,q.push((node){s,d+1}),n-=(k-1);
    }
    printf("%lld\n%d",ans,q.top().h-1);
}

巴特西

Luogu P2168 [NOI2015]荷马史诗

最新文章

热门文章