题意
??给定n个单词的出现次数，将这
n 个单词用n个k 进制字符串代替这n个单词，要求任意一个字符串不是另一个字符串的前缀
求出一种方案使得替换后的总长度最小，在总长度最小的前提下，尽量使最长字符串的长度变小
题解
??如果是以前学过哈夫曼树的人，应该能够一眼看出这就是
k 进制哈夫曼树
??因为当(n?1)%(k?1)!=0时，哈夫曼树会不满，所以我们加入k?1?(n?1)%(k?1)个权为0的点以方便解题
??使用哈夫曼树能够轻易的满足第一个条件：总长度最小。为了使第二个条件也满足，我们考虑将一个点变成一个二元组：（点权，深度）（所有点初始深度为0），先按点权从小到大，点券相同就按深度从小到大
??然后使用优先队列存点，在合并时，新节点的深度就是选出的k个点的深度的最大值+1，然后将新节点丢入队列中，如此反复，知道队列中只剩下一个元素时停止
??第二问的答案很好求，最长字符串的长度就是最后剩下的点的深度；考虑怎么统计总长度：在合并的过程中（一开始将初始点兑入队列中不算），每往队列中丢入一个元素，ans+=sum（sum为该元素的点权），这样的话，第i层的点的点权会被加上i 次，就相当于是出现次数*字符串长度，因此这样得到的答案就是总长度
复杂度
O(nlogn)
代码
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<queue>
#define Rint register int
#define Lint long long int
using namespace std;
const int N=100010;
struct node
{Lint val;int dep;bool operator < (const node &a) const{return val==a.val ? dep>a.dep:val>a.val;}
};
Lint w[N],ans;
int n,k,l;
priority_queue<node> q;
int main()
{scanf("%d%d",&n,&k);for(int i=1;i<=n;i++) scanf("%lld",&w[i]);sort( w+1,w+n+1 );for(int i=1;i<=n;i++) q.push( (node){ w[i],0 } );while( (n-1)%(k-1) ) q.push( (node){ 0,0 } ),n++;while( q.size()>1 ){Lint sum=0;int num=1,mx=0;while( num<=k ){sum+=q.top().val;num++,mx=max( mx,q.top().dep );q.pop();}ans+=sum;q.push( (node){ sum,mx+1 } );}printf("%lld\n",ans);printf("%d\n",q.top().dep);return 0;
}