题意：一部《荷马史诗》中有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<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#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 ppx{
ll val,deep;
bool operator <(const ppx &x)const{
return val==x.val?deep>x.deep:val>x.val;
}
}temp;
priority_queue<ppx>q;
inline void huffman(ll n,ll k){
ll ans=0;
while(n>1){
ll tot=0,max_deep=0;
for(ll i=1;i<=k;++i){
temp=q.top();q.pop();
tot+=temp.val;
max_deep=max(max_deep,temp.deep);
}
ans+=tot;n=n-(k-1);
temp.val=tot;temp.deep=max_deep+1;q.push(temp);
}
printf("%lld
%lld
",ans,q.top().deep);
}
int main(){
ll n=read(),k=read();
for(ll i=1;i<=n;++i){
ll x=read();
temp.val=x;temp.deep=0;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=0;q.push(temp);
}
huffman(n,k);
return 0;
}