[NOI2015]荷马史诗

洛咕

BZOJ

题意：一部《荷马史诗》中有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 ）的整数。

分析：第一问是Huffman树的模板题。第二问只要在求Huffman树时，对于权值相同的节点，优先考虑当前深度最小的节点合并即可，具体来说就是重载运算符排序时写成\(val==x.val?deep>x.deep:val>x.val\)而不是简单的\(val>x.val\);

//#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#define LL long long
using namespace std;
inline LL read(){
    LL x=0,o=1;char ch=getchar();
    while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
    if(ch=='-')o=-1,ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*o;
}
struct node{
    LL val,deep;
    bool operator <(const node &x)const{
        return val==x.val?deep>x.deep:val>x.val;
    }
}temp;
priority_queue<node>q;
inline void Huffman(LL n,LL k){
    LL ans=0;
    while(n>1){
        LL max_deep=0,tot=0;
        for(LL i=1;i<=k;++i){
            temp=q.top();q.pop();
            tot+=temp.val;max_deep=max(max_deep,temp.deep);
        }
        temp.val=tot;temp.deep=max_deep+1;q.push(temp);
        ans+=tot;n-=k-1;
    }
    printf("%lld\n%lld\n",ans,q.top().deep-1);
}
int main(){
    LL n=read(),k=read();
    for(LL i=1;i<=n;++i){
        LL v=read();
        temp.val=v;temp.deep=1;q.push(temp);
    }
    LL res=(n-1)%(k-1);
    if(res!=0)res=k-1-res,n+=res;
    for(LL i=1;i<=res;++i)temp.val=0,temp.deep=1,q.push(temp);
    Huffman(n,k);
    return 0;
}

[NOI2015]荷马史诗

原文：https://www.cnblogs.com/PPXppx/p/11246424.html