NOI2015荷马史诗
一部《荷马史诗》中有 n 种不同的单词，从 1 到 n 进行编号。其中第 i 种单词出现的总次数为 wi。Allison 想要用 k 进制串 si 来替换第 i 种单词，使得其满足如下要求
对于任意的 1≤i,j≤n，i≠j，都有：si 不是 sj 的前缀
在 Allison 想要知道，如何选择 si，才能使替换以后得到的新的《荷马史诗》长度最小。在确保总长度最小的情况下，Allison 还想知道最长的 si 的最短长度是多少？
输入文件的第 1 行包含 2 个正整数 n,k，中间用单个空格隔开，表示共有 n 种单词，需要使用 k 进制字符串进行替换。
接下来 n 行，第 i+1 行包含 1 个非负整数 wi，表示第 i 种单词的出现次数。
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 #define ll long long 5 6 ll n,k,ans; 7 8 struct node{ 9 ll val,dep; 10 node(){} 11 node(ll _,ll __){val=_,dep=__;} 12 }tmp; 13 14 bool operator <(node x,node y){return x.val>y.val||(x.val==y.val&&x.dep>y.dep);} 15 16 priority_queue<node> q; 17 18 ll readin() 19 { 20 ll x=0;char ch=getchar(); 21 while(ch<‘0‘||ch>‘9‘) ch=getchar(); 22 while(ch>=‘0‘&&ch<=‘9‘) x=x*10+(ll)(ch-‘0‘),ch=getchar(); 23 return x; 24 } 25 26 void work() 27 { 28 while(n>1){ 29 ll maxd=0,tot=0; 30 for(ll i=1;i<=k;i++){ 31 tmp=q.top();q.pop(); 32 tot+=tmp.val; 33 maxd=max(maxd,tmp.dep); 34 } 35 q.push(node(tot,maxd+1)); 36 ans+=tot;n-=k-1; 37 } 38 printf("%lld\n%lld\n",ans,q.top().dep-1); 39 } 40 41 void init() 42 { 43 n=readin();k=readin(); 44 for(ll i=1;i<=n;i++) q.push(node(readin(),1)); 45 ll remain=(n-1)%(k-1); 46 if(remain!=0) remain=k-1-remain,n+=remain; 47 for(ll i=1;i<=remain;i++) q.push(node(0,1)); 48 } 49 50 int main() 51 { 52 init(); 53 work(); 54 return 0; 55 }
原文：https://www.cnblogs.com/aininot260/p/9643763.html