荷马史诗 NOI2015 解析

比较简单，这道题需要贪心解决。

不需要任何复杂的数据结构，一个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=;

type rec=record

       num,deep:int64;

     end;

var n,k,i,j,tot:longint;ans,mxdep:int64;

    node,now:rec;

    a:array[..maxn]of int64;

    q:array[..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> do begin

  if (q[x].num>q[x div ].num)or((q[x].num=q[x div ].num)and(q[x].deep>q[x div ].deep))//注意多判断深度

  then break;

  swap(q[x],q[x div ]);

  x:=x div ;

 end;

end;

procedure down(x:longint);

var lson,rson,son,pd:longint;

begin

 while x<tot do begin

  lson:=*x; //pd=;

  rson:=*x+;  //pd=;

  pd:=;

  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:=;

  if pd= 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:= to n do read(a[i]);

 if k<> then

  while n mod (k-)<> do begin

   inc(n); a[n]:=;

  end;//如果不是2叉堆需要初始化保证huffman树最后一层的元素到达k个，方便操作

 tot:=;

 for i:= to n do begin

  inc(tot);

  q[tot].num:=a[i];

  q[tot].deep:=;

  up(tot);

 end;//建堆

 while tot<> do begin

  node.num:=;node.deep:=; mxdep:=;//k个元素的和、深度、最大深度

  for i:= to k do begin

   now:=q[];

   swap(q[],q[tot]);

   dec(tot);

   down();

   node.num:=node.num+now.num;

   mxdep:=max(mxdep,now.deep);

  end;//由于是k进制所以需要取出堆中k个元素

  ans:=ans+node.num;//累加

  node.deep:=mxdep+;//深度++

  inc(tot);

  q[tot]:=node;

  up(tot);//放回去

 end;

 writeln(ans);

 writeln(mxdep+);//打印

end.

巴特西

荷马史诗 NOI2015 解析

最新文章

热门文章