专栏首页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 条评论
登录 后参与评论

相关文章

  • 算法模板——splay区间反转 2

    实现功能:同splay区间反转 1(基于BZOJ3223 文艺平衡树) 这次改用了一个全新的模板(HansBug:琢磨了我大半天啊有木有),大大简化了程序,同时...

    HansBug
  • 3224: Tyvj 1728 普通平衡树

    3224: Tyvj 1728 普通平衡树 Time Limit: 10 Sec  Memory Limit: 128 MB Submit: 2566  Sol...

    HansBug
  • 算法模板——平衡树Treap

    实现功能如下——1. 插入x数 2. 删除x数(若有多个相同的数,因只删除一个) 3. 查询x数的排名(若有多个相同的数,因输出最小的排名) 4. 查询排名为x...

    HansBug
  • 算法模板——splay区间反转 2

    实现功能:同splay区间反转 1(基于BZOJ3223 文艺平衡树) 这次改用了一个全新的模板(HansBug:琢磨了我大半天啊有木有),大大简化了程序,同时...

    HansBug
  • nodejs使用superagent爬取网站内容中文乱码的解决方法

    使用superagent爬取网站内容,当网页编码不是utf-8编码时,中文就会返回乱码,原因是superagent只支持utf-8的网页编码,我们可以使用其扩展...

    飞奔去旅行
  • 8.11 VR扫描:Oculus 将延长夏日促销活动时间;HTC推限量版《英雄防线》Vive套装

    VRPinea
  • curl扩展post请求http接口报错:failed creating formpost data

    使用curl_error($ch) 查看错误信息 , 返回的错误信息是: failed creating formpost data

    陶士涵
  • 解决Linux环境下Tomcat日志乱码的问题

    Linux上部的Tomcat服务器中部署了Java Web应用,查看日志的时候发现里面的中文全部是乱码,把文件拖拽到本地Windows上全是问号。从其他系统拽过...

    飞奔去旅行
  • 【星球知识卡片】模型蒸馏的核心技术点有哪些,如何对其进行长期深入学习

    一般地,大模型往往是单个复杂网络或者是若干网络的集合,拥有良好的性能和泛化能力,而小模型因为网络规模较小,表达能力有限。利用大模型学习到的知识去指导小模型训练,...

    用户1508658
  • Redis List 类型操作及常用命令

    list 是一个链表结构,主要功能是 push、 pop、获取一个范围的所有值等等, 操作中 key 理解为链表的名字。

    Jacob丶

扫码关注云+社区

领取腾讯云代金券