专栏首页HansBug's Lab1112: [POI2008]砖块Klo

1112: [POI2008]砖块Klo

1112: [POI2008]砖块Klo

Time Limit: 10 Sec  Memory Limit: 162 MB

Submit: 1245  Solved: 426

[Submit][Status][Discuss]

Description

N柱砖,希望有连续K柱的高度是一样的. 你可以选择以下两个动作 1:从某柱砖的顶端拿一块砖出来,丢掉不要了. 2:从仓库中拿出一块砖,放到另一柱.仓库无限大. 现在希望用最小次数的动作完成任务.

Input

第一行给出N,K. (1 ≤ k ≤ n ≤ 100000), 下面N行,每行代表这柱砖的高度.0 ≤ hi ≤ 1000000

Output

最小的动作次数

Sample Input

5 3 3 9 2 3 1

Sample Output

2

HINT

原题还要求输出结束状态时,每柱砖的高度.本题略去.

Source

题解:(呵呵呵我会说我逗到了用Splay做这题的地步么= =)

首先,看这道题,对于某个高度序列而言,很明显将所有高度都变为中位数代价最小

我觉得任何一个数竞党都该知道怎么样可以让下列式子值最小——

\( \sum_{i=1}^{N} \left | x-x_i \right | \) 其中,\( x_1 \leq x_2 \leq x_3 ... \leq x_N \) 显然,当N为奇数时, \( x=x_\frac{N+1}{2} \) 当N为偶数时, \( x_\frac{N}{2} \leq x \leq x_\frac{N+2}{2} \)

然后接下来讨论怎么实现——我们需要一棵平衡树,可以加入和删除值,可以查询指定排名的数位置(用来找中位数),还得可以快速求出当前序列中比中位数大的各个数之和,以及比它小的之和,这样子就很明显需要维护子树大小(用于排名),然后还得维护子树和,然后我为了偷懒就直接来了个splay,每次将中位数splay上来,然后两边的不就是我们要的两边和嘛,然后该怎么办怎么办,别的没了

  1 /**************************************************************
  2     Problem: 1112
  3     User: HansBug
  4     Language: Pascal
  5     Result: Accepted
  6     Time:6156 ms
  7     Memory:27636 kb
  8 ****************************************************************/
  9  
 10 var
 11    i,j,k,m,n,head:longint;
 12    l,ans:int64;
 13    lef,rig,b:array[0..1000000] of longint;
 14    a,c:array[0..1000000] of int64;
 15 procedure rt(var x:longint);inline;
 16           var f,l:longint;
 17           begin
 18                if (x=0) or (lef[x]=0) then exit;
 19                b[lef[x]]:=b[x];b[x]:=b[rig[lef[x]]]+b[rig[x]]+1;
 20                c[lef[x]]:=c[x];c[x]:=c[rig[lef[x]]]+c[rig[x]]+a[x];
 21                f:=x;l:=lef[x];
 22                lef[f]:=rig[l];
 23                rig[l]:=f;
 24                x:=l;
 25           end;
 26 procedure lt(var x:longint);inline;
 27           var f,r:longint;
 28           begin
 29                if (x=0) or (rig[x]=0) then exit;
 30                b[rig[x]]:=b[x];b[x]:=b[lef[rig[x]]]+b[lef[x]]+1;
 31                c[rig[x]]:=c[x];c[x]:=c[lef[rig[x]]]+c[lef[x]]+a[x];
 32                f:=x;r:=rig[x];
 33                rig[f]:=lef[r];
 34                lef[r]:=f;
 35                x:=r;
 36           end;
 37 procedure splay(var x:longint;y:longint);inline;
 38           begin
 39                if (x=0) or (y=0) then exit;
 40                if y=(b[lef[x]]+1) then exit;
 41                if y<(b[lef[x]]+1) then
 42                   begin
 43                        if (b[lef[lef[x]]]+1)=y then rt(x) else
 44                           if y<(b[lef[lef[x]]]+1) then
 45                              begin
 46                                   splay(lef[lef[x]],y);
 47                                   rt(x);rt(x);
 48                              end
 49                           else
 50                               begin
 51                                    splay(rig[lef[x]],y-b[lef[lef[x]]]-1);
 52                                    lt(lef[x]);rt(x);
 53                               end;
 54                   end
 55                else
 56                    begin
 57                         y:=y-1-b[lef[x]];
 58                         if y=(b[lef[rig[x]]]+1) then lt(x) else
 59                            if y<(b[lef[rig[x]]]+1) then
 60                               begin
 61                                    splay(lef[rig[x]],y);
 62                                    rt(rig[x]);lt(x);
 63                               end
 64                            else
 65                                begin
 66                                     splay(rig[rig[x]],y-1-b[lef[rig[x]]]);
 67                                     lt(x);lt(x);
 68                                end;
 69                    end;
 70           end;
 71 procedure ins(var x:longint;y:longint);inline;
 72           begin
 73                if x=0 then
 74                   begin
 75                        x:=y;
 76                        exit;
 77                   end;
 78                if a[y]<=a[x] then
 79                   begin
 80                        ins(lef[x],y);
 81                        c[x]:=c[lef[x]]+c[rig[x]]+a[x];
 82                        b[x]:=b[lef[x]]+b[rig[x]]+1;
 83                   end
 84                else
 85                    begin
 86                         ins(rig[x],y);
 87                         c[x]:=c[lef[x]]+c[rig[x]]+a[x];
 88                         b[x]:=b[lef[x]]+b[rig[x]]+1;
 89                    end;
 90           end;
 91 function getrank(x,y:longint):longint;inline;
 92          begin
 93               if x=0 then exit(-1);
 94               if a[x]=y then exit(b[lef[x]]+1);
 95               if y<a[x] then exit(getrank(lef[x],y)) else exit(b[lef[x]]+1+getrank(rig[x],y));
 96          end;
 97 procedure init(x:longint);inline;
 98           begin
 99                ins(head,x);
100                splay(head,random(b[head])+1);
101           end;
102 procedure kill(x:longint);inline;
103           begin
104                if x=1 then
105                   begin
106                        splay(head,2);
107                        dec(c[head],c[lef[head]]);
108                        dec(b[head]);
109                        lef[head]:=0;
110                   end
111                else if x=b[head] then
112                     begin
113                          splay(head,b[head]-1);
114                          dec(c[head],c[rig[head]]);
115                          dec(b[head]);
116                          rig[head]:=0;
117                     end
118                else begin
119                          splay(head,x+1);
120                          splay(lef[head],x-1);
121                          dec(c[head],c[rig[lef[head]]]);dec(b[head]);
122                          dec(c[lef[head]],c[rig[lef[head]]]);dec(b[lef[head]]);
123                          rig[lef[head]]:=0;
124                     end;
125           end;
126 begin
127      readln(n,m);randomize;
128      if m<=1 then
129         begin
130              writeln(0);
131              halt;
132         end;
133      for i:=1 to n do
134          begin
135               readln(a[i]);
136               c[i]:=a[i];b[i]:=1;
137               lef[i]:=0;rig[i]:=0;
138          end;
139      head:=0;ans:=maxlongint*maxlongint;
140      for i:=1 to m do init(i);
141      for i:=1 to n-m+1 do
142          begin
143               splay(head,(m+1) div 2);
144               l:=0;
145               if lef[head]<>0 then inc(l,a[head]*b[lef[head]]-c[lef[head]]);
146               if rig[head]<>0 then inc(l,c[rig[head]]-a[head]*b[rig[head]]);
147               if l<ans then ans:=l;
148               if i=(n-m+1) then break;
149               kill(getrank(head,a[i]));
150               init(i+m);
151          end;
152      writeln(ans);
153      readln;
154 end.

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Python入门进阶教程-JSON操作

    当程序把 JSON 对象或 JSON 字符串转换成 Python 对象时,从 JSON 类型到 Python 类型的转换关系如下所示:

    小一不二三
  • 揭秘字节跳动埋点数据实时动态处理引擎(附源码)

    宝贝们,还记得前几天博主去的火山引擎大数据场嘛,其中比较令大家感兴趣的就是最后一讲,字节一站式埋点平台的 flink 标准化清洗及拆流任务。

    公众号:大数据羊说
  • 美团外卖Android Crash治理之路

    Crash率是衡量一个App好坏的重要指标之一。如果你忽略了它的存在,它就会得寸进尺,愈演愈烈,最后造成大量用户的流失,进而给公司带来无法估量的损失。本文讲述美...

    美团技术团队

扫码关注云+社区

领取腾讯云代金券