1112: [POI2008]砖块Klo
1112: [POI2008]砖块Klo
HansBug
发布于 2018-04-11 11:07:55
发布于 2018-04-11 11:07:55
1112: [POI2008]砖块Klo
Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 1245 Solved: 426
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.本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2015-05-10 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录