Vijos 1507 郁闷的出纳员 解题报告

这是一道很经典的数据结构题，标准解法是平衡树，但也可以用线段树和树状数组来做。

 

树状数组解法：

用c[i]表示工资在[i-lowbit(i)+1,i]区间的人数，显然插入就是对每个包含k+d（用于维护新加入人员与原有人员之间的工资增减差额，是本题实现的一个非常巧妙的技巧）的区间元素+1，删除则是将包含c[min+d..min+d+k-1]所在区间的区间元素减去相应的人数。以下是删除部分的代码：

 

procedure delete(now,k:longint);
begin
  while now<=maxn do
    begin
      dec(c[now],k); inc(now,lowbit(now));
    end;
end;

 

for j:=min+d to min+d+k-1 do
  if c[j]>0 then
    begin
      inc(ans,c[j]); delete(j,c[j]);
    end;
inc(d,k);

 

关键在于如何求第k大工资，实际上我们是将其转化为求第total（现有员工数）-k+1小的工资。假设f[i]表示工资小于等于i的现有员工人数，则我们现在所需要求的实际上就是满足f[i]>=total-k+1的最小的i值。因此很容易想到一个每次查询复杂度为O(log n*log n)的算法，即二分工资并利用树状数组求出工资小于等于当前工资的人数。但这种算法还是没能完全利用树状数组的储存特性，假设所求的最小的i值为ans'，则改进算法的核心思想实际上就是将ans'分割成一段段长度为2的倍数的区间累加逼近。由于不太好说明，请结合代码进行理解：

 

function getkth(k:longint):longint;
var now,p,s:longint;
begin
  if total-ans<k then exit(-1);
  k:=total-ans-k+1; now:=0; p:=0; s:=1 shl 18;
  while (now<k) and (s>0) do
    begin
      while (c[p+s]+now>=k) and (s>0) do s:=s shr 1;
      if s=0 then break;
      inc(p,s); inc(now,c[p]);
    end;
  exit(p+1-d);
end;

 

另外由于Vijos对于大数据的处理存在缺陷，本题的输出不能换行，否则会导致TLE（我多交了3次后的忠告）......

 

R1147973 Accepted 100 From IwfWcf－ P1507 FPC Vivid Puppy 2009-2-17 1:15:05

 

平衡树解法：

我是用SBT退化版来写的，整个程序只有82行。做法同样是利用一个变量d来维护新加入人员与原有人员之间的工资增减差额关系，新增员工即插入一个节点，统计每次扣工资后员工离开的数量即删除工资最接近min+d的子树后统计根节点的size域的减少量。代码如下：

 

procedure delete(var t:longint;v:longint);
begin
  if t=0 then exit;
  if key[t]<v then
    begin
      t:=r[t]; delete(t,v);
    end
    else delete(l[t],v);
  if t>0 then s[t]:=s[l[t]]+s[r[t]]+1;
end;

 

inc(d,k); ltotal:=s[root];
delete(root,min+d); inc(ans,ltotal-s[root]);

 

求第k大的工资实际上即转化为求第total(当前员工总数)-k+1小的工资是多少，这是SBT本身即支持的操作。