题目：洛谷P2168、codevs5501。
题目大意：
有n种单词，每种单词有一个出现次数。现在要用k进制字符串代表这些单词，使得任意一个字符串不是另一个的前缀。问：最短的总长度是多少？最短的单词长度是多少？
解题思路：
哈夫曼编码构造过程，k进制就每次取k个合并。
用优先队列实现即可。
注意：最后合并时可能出现不够，所以可以一开始增加一些空节点占位。
C++ Code：
#include<bits/stdc++.h>
#include<ext/pb_ds/priority_queue.hpp>
#define LoveLive long long
using namespace std;
__gnu_pbds::priority_queue<pair<LoveLive,int>,greater<pair<LoveLive,int> >,__gnu_pbds::pairing_heap_tag>h;
int n,k;
inline LoveLive readint(){
int c=getchar();
LoveLive d=0;
for(;!isdigit(c);c=getchar());
for(;isdigit(c);c=getchar())d=(d<<3)+(d<<1)+(c^‘0‘);
return d;
}
int main(){
n=readint(),k=readint();
for(int i=1;i<=n;++i)h.push(make_pair(readint(),1));
if((n-1)%(k-1))
for(int i=k-1-(n-1)%(k-1);i;--i)h.push(make_pair(0ll,1));
LoveLive niconiconi=0;
for(int tot=n+(((n-1)%(k-1))?k-1-(n-1)%(k-1):0);tot>1;tot-=k-1){
int mx=0;
LoveLive sm=0;
for(int i=1;i<=k;++i){
pair<LoveLive,int>p=h.top();
h.pop();
mx=max(mx,p.second);
sm+=p.first;
}
niconiconi+=sm;
h.push(make_pair(sm,mx+1));
}
printf("%lld\n%d\n",niconiconi,h.top().second-1);
}
原文：https://www.cnblogs.com/Mrsrz/p/9157256.html