比较简单，这道题需要贪心解决。
不需要任何复杂的数据结构，一个luo的堆就足够了。
本题的意思就是：给定n种单词及在文本中各自出现的频率，要求利用二进制串对其进行前缀编码，使得压缩后的文本长度最短。
改用k进制串？最长的单个单词编码最短？
我们知道有个叫huffman编码的东西就是来解决这类编码问题的。所以尝试用huffman思想去解题。
如果编码的进制是2进制就好了，但是题目的数据只有少部分是2进制编码的，
所以我们要仿造二叉形式huffman一次弹出两个(最小值)成k叉一次弹出k个(最小值);
二叉堆来实现（不是用k叉堆，这样做时间复杂度太高且不易实现）
每一次弹出最值时就是连续取二叉堆的前k个数就可以了。
堆中保存Huffman树中串出现频率和，以及Huffman树的深度;
比较时先比较频率和，再比较深度(不可不比，要保证Huffman树高最小);
每次合并时，ans都要加上合并后长度(要不然求的是串频率和)，而深度在取最大后再插入时要加1;
当堆中只有一个元素时退出，这时，ans和该元素深度即为答案;
注意到初始化堆的时候最后一层到不了k个怎么办？
初始化时注意各元素深度为0，若n!≡1mod(k-1)，那么补齐n，增加的新元素频率为0(显然)，深度为0;
堆的建立就不详细说了。
uses math; const maxn=100010; type rec=record num,deep:int64; end; var n,k,i,j,tot:longint;ans,mxdep:int64; node,now:rec; a:array[1..maxn]of int64; q:array[1..maxn]of rec; procedure swap(var a,b:rec); var t:rec; begin t:=a; a:=b; b:=t; end; procedure up(x:longint); begin while x>1 do begin if (q[x].num>q[x div 2].num)or((q[x].num=q[x div 2].num)and(q[x].deep>q[x div 2].deep))//注意多判断深度 then break; swap(q[x],q[x div 2]); x:=x div 2; end; end; procedure down(x:longint); var lson,rson,son,pd:longint; begin while x<tot do begin lson:=2*x; //pd=1; rson:=2*x+1; //pd=2; pd:=1; if lson>tot then break; if (lson<tot)and((q[lson].num>q[rson].num)or(q[lson].num=q[rson].num)and(q[lson].deep>q[rson].deep)) then pd:=2; if pd=1 then son:=lson else son:=rson; if (q[x].num<q[son].num)or((q[x].num=q[son].num)and(q[x].deep<q[son].deep)) then break; swap(q[x],q[son]); x:=son; end; end; begin readln(n,k); for i:=1 to n do read(a[i]); if k<>2 then while n mod (k-1)<>1 do begin inc(n); a[n]:=0; end;//如果不是2叉堆需要初始化保证huffman树最后一层的元素到达k个，方便操作 tot:=0; for i:=1 to n do begin inc(tot); q[tot].num:=a[i]; q[tot].deep:=0; up(tot); end;//建堆 while tot<>1 do begin node.num:=0;node.deep:=0; mxdep:=0;//k个元素的和、深度、最大深度 for i:=1 to k do begin now:=q[1]; swap(q[1],q[tot]); dec(tot); down(1); node.num:=node.num+now.num; mxdep:=max(mxdep,now.deep); end;//由于是k进制所以需要取出堆中k个元素 ans:=ans+node.num;//累加 node.deep:=mxdep+1;//深度++ inc(tot); q[tot]:=node; up(tot);//放回去 end; writeln(ans); writeln(mxdep+1);//打印 end.