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

相关文章

来自专栏C语言及其他语言

OJ系统(ACM/NOI)的基本输入输出教程

在介绍OJ系统之前,首先为大家介绍一下ACM: ACM原代表美国计算机协会,因其举办的ICPC即国际大学生程序设计竞赛而闻名全世界,此项赛事要求学生的在五小时内...

55212
来自专栏ml

hdu-----(4514)湫湫系列故事——设计风景线(树形DP+并查集)

湫湫系列故事——设计风景线 Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 65535/3276...

3938
来自专栏技术博客

设计模式之前奏(UML类图)

本人菜菜一个,最近一直在博客园游走闲逛,看到了各种技术,各种各种……。便看到了大话设计模式这本书,下了电子版的看了看第一章,感觉相当不错,不仅通俗易懂,而且与实...

2283
来自专栏数据结构与算法

BZOJ2152: 聪聪可可(点分治)

聪聪和可可是兄弟俩,他们俩经常为了一些琐事打起来,例如家中只剩下最后一根冰棍而两人都想吃、两个人都想玩儿电脑(可是他们家只有一台电脑)……遇到这种问题,一般情况...

1003
来自专栏我和未来有约会

[Silverlight动画]转向行为 - 对象回避

对象回避主题的完整意义是指,在机车行走的路线中存在一些障碍物,机车必须绕开、防止触碰到它们。听上去和碰撞检测有关,然而这仅仅是发生在预测阶段,也就是:“以我当前...

2075
来自专栏架构说

110. 平衡二叉树

世界分为三条线,两实一虚: 1. 当前时间线: 黑帽威廉时间线,凡是有黑帽威廉的都在当前时间 2. 历史时间线:白帽威廉时间线 (35年前),凡是有白帽威廉的都...

1002
来自专栏数据结构与算法

Day3上午解题报告

预计分数:100+40+50=190 实际分数:100+40+50=190 T1 https://www.luogu.org/problem/show?pid=...

2985
来自专栏数据结构与算法

BZOJ2659: [Beijing wc2012]算不出的算式(数学)

985
来自专栏C语言及其他语言

【每日一题】问题 1146: 舍罕王的失算

关注我们 题目描述 相传国际象棋是古印度舍罕王的宰相达依尔发明的.舍罕王十分喜爱象棋,决定让宰相自己选择何种赏赐.这位聪明的宰相指着8*8共64格的象棋说:陛...

35111
来自专栏点滴积累

PhiloGL学习(6)——深情奉献:快乐的一家

 前言 话说上一篇文章结尾讲到这一篇要做一个地球自转以及月球公转的三维动画,提笔,不对,是提键盘开始写的时候脑海中突然出现了几年前春晚风靡的那首歌:蒙古族小丫头...

3464

扫码关注云+社区

领取腾讯云代金券