用 X(k) 表示 X 是以 k 进制表示的字符串。
一种最优方案：令 00(2) 替换第 1 种单词，01(2) 替换第 2 种单词，10(2) 替换第 3 种单词，11(2) 替换第 4 种单词。在这种方案下，编码以后的最短长度为：
1×2+1×2+2×2+2×2=12
最长字符串 si 的长度为 2。
一种非最优方案：令 000(2) 替换第 1 种单词，001(2) 替换第 2 种单词，01(2) 替换第 3 种单词，1(2) 替换第 4 种单词。在这种方案下，编码以后的最短长度为：
1×3+1×3+2×2+2×1=12
最长字符串 si 的长度为 3。与最优方案相比，文章的长度相同，但是最长字符串的长度更长一些。
对于所有数据，保证 2≤n≤100000，2≤k≤9。
选手请注意使用 64 位整数进行输入输出、存储和计算。
题解：因为要保证Si不为Sj的前缀。所以就可以想到哈夫曼编码。然后发现当k=2是就是合并果子。其实k叉树的做法也是一样的。每次去最小的k个合并即可。发现只有当(n-1)%(k-1)=0的时候才能恰好合并，，所以要添加k-1-(n-1)%(k-1)个权值为0高度为1的虚拟节点。然后用堆维护一下最小值就好了。为了保证最大高度最小，我们把高度加进比较的第二关键字。
#include<iostream>#include<cstdio>#include<algorithm>#include<queue>using namespace std;struct use{long long v,h;};bool operator<(use a,use b){if (a.v!=b.v) return a.v>b.v;else return a.h>b.h; }priority_queue<use>q;int n,k,top(0);long long ans(0),hh,x;int main(){scanf("%d%d",&n,&k);for (int i=1;i<=n;i++){use temp;scanf("%lld",&x);temp.v=x;temp.h=1;q.push(temp);} if ((n-1)%(k-1)!=0) top=k-1-(n-1)%(k-1); for (int i=1;i<=top;i++){use temp;temp.v=0;temp.h=1;q.push(temp);}top+=n;while (top!=1){use a;long long temp(0),maxx(0);for (int i=1;i<=k;i++){a=q.top();temp+=a.v;maxx=max(a.h,maxx);q.pop();}ans+=temp;a.v=temp;a.h=maxx+1;q.push(a);top-=k-1;}hh=q.top().h-1;cout<<ans<<endl<<hh<<endl;}
可见内心底对旅行是多么的淡漠。
