追逐影子的人，自己就是影子 ——荷马
Allison最近迷上了文学。她喜欢在一个慵懒的午后，细细地品上一杯卡布奇诺，静静地阅读她爱不释手的《荷马史诗》。但是由《奥德赛》和《伊利亚特》组成的鸿篇巨制《荷马史诗》实在是太长了，Allison想通过一种编码方式使得它变得短一些。
一部《荷马史诗》中有 n 种不同的单词，从 1 到 n 进行编号。其中第 i 种单词出现的总次数为 w[i] 。Allison想要用 k 进制串 s[i] 来替换第 i 种单词，使得其满足如下要求：
对于任意的 1<=i,j<=n ， i<>j ，都有： s[i] 不是 s[j] 的前缀。
现在Allison想要知道，如何选择 s[i] ，才能使替换以后得到的新的《荷马史诗》长度最小。在确保总长度最小的情况下，Allison还想知道最长的 s[i] 的最短长度是多少？
一个字符串被称为 k 进制字符串，当且仅当它的每个字符是 0 到 k-1 之间（包括 0 和 k−1 ）的整数。
字符串 Str1 被称为字符串 Str2 的前缀，当且仅当：存在 1<=t<=m ，使得 Str1 = Str2[1..t] 。其中， m 是字符串 str2 的长度， str2[1..t] 表示 str2 的前 t 个字符组成的字符串。
输入文件的第 1 行包含 2 个正整数 n,k ，中间用单个空格隔开，表示共有 n 种单词，需要使用 k 进制字符串进行替换。
接下来 n 行，第 i+1 行包含 1 个非负整数 w[i] ，表示第 i 种单词的出现次数。
输出文件包括 2 行。 第 1 行输出 1 个整数，为《荷马史诗》经过重新编码以后的最短长度。 第 2 行输出 1 个整数，为保证最短总长度的情况下，最长字符串 s[i] 的最短长度。
题目简述
k-进制哈夫曼编码
题解
容易得到每次都是选取最小的k个合并，如果大小相同，要选取编码长度短的
开始要先把一些合并起来，才能使答案最优，原因就不赘述了
#include<stdio.h> #include<stdlib.h> #include<iostream> #include<string> #include<string.h> #include<algorithm> #include<math.h> #include<queue> #include<map> #include<vector> #include<set> #define il inline #define re register #define min(a,b) ((a)<(b)?(a):(b)) #define max(a,b) ((a)>(b)?(a):(b)) using namespace std; const int N=100001; typedef long long ll; int n,k,hs; struct data{int w;ll v;} h[N]; il ll read(){re ll hs=0;re char c=getchar();while(!isdigit(c)) c=getchar();while(isdigit(c)){hs=(hs<<3)+(hs<<1)+c-'0';c=getchar();}return hs; } il bool cmp(re data a,re data b){return (a.v==b.v)?(a.w<b.w):(a.v<b.v); } il void swim(re int p){re int q=p>>1;re data a=h[p];while(q>0&&cmp(a,h[q])){h[p]=h[q];p=q;q=p>>1;}h[p]=a; } il void sink(re int p){re int q=p<<1;re data a=h[p];while(q<=hs){if(q<hs&&cmp(h[q+1],h[q])) q++;if(cmp(a,h[q])) break;h[p]=h[q];p=q;q=p<<1;}h[p]=a; } il void insert(re data v){h[++hs]=v;swim(hs); } il void pop(){h[1]=h[hs--];sink(1); } int main(){n=read();k=read();for(int i=1;i<=n;i++){h[i].v=read();h[i].w=1;}sort(h+1,h+n+1,cmp);hs=n;re ll ans=0,cnt=0;re int maxn;if((n-1)%(k-1)>0){for(int i=1;i<=(n-1)%(k-1)+1;i++){cnt+=h[1].v;// print(); pop();}insert((data){2,cnt});ans=cnt;}while(hs>1){cnt=0;maxn=0;for(int i=1;i<=k;i++){cnt+=h[1].v;maxn=max(maxn,h[1].w);pop();// print(); }insert((data){maxn+1,cnt});// print();ans+=cnt;}cout<<ans<<endl<<h[1].w-1<<endl;return 0; }
