传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=1112
题目大意：N柱砖,希望有连续K柱的高度是一样的. 你可以选择以下两个动作 1:从某柱砖的顶端拿一块砖出来,丢掉不要了. 2:从仓库中拿出一块砖,放到另一柱.仓库无限大. 现在希望用最小次数的动 作完成任务.
题解：我们看看n是10
6于是我们可以枚举k，是O（n）的，那么看看时间复杂度，就需要一个logN的算法来删除一个数，加入一个数，寻找第k个数，于是平衡树即可！时间复杂度：NlogN；
实际上刚开始想的是二分次数+二分长度，想想应该也是可行的，只不过在答案验证上，可以自己想想，反正我不知道！
1 #include<iostream>
2 #include<cstring>
3 #include<cstdio>
4 #include<algorithm>
5 #include<cmath>
6 #define maxn 100005
7 #define ll long long
8 #define linf 9223372036854775807LL
9 using namespace std;
10 int n,k,root,mid,mmid,sz;
11 ll tmp;
12 ll sum1,sum2,ans;
13 int a[maxn];
14 int ls[maxn],rs[maxn],size[maxn],w[maxn],rnd[maxn];
15 ll sum[maxn],v[maxn];
16 int read()
17 {
18 int x=
0;
char ch;
bool bo=
0;
19 while (ch=getchar(),ch<
'0'||ch>
'9')
if (ch==
'-') bo=
1;
20 while (x=x*
10+ch-
'0',ch=getchar(),ch>=
'0'&&ch<=
'9');
21 if (bo)
return -x;
return x;
22 }
23 void updata(
int k)
24 {
25 sum[k]=sum[ls[k]]+sum[rs[k]]+w[k]*
v[k];
26 size[k]=size[ls[k]]+size[rs[k]]+
w[k];
27 }
28 void rturn(
int &
k)
29 {
30 int t=ls[k]; ls[k]=rs[t]; rs[t]=k; updata(k); updata(t); k=t;
return;
31 }
32 void lturn(
int &
k)
33 {
34 int t=rs[k]; rs[k]=ls[t]; ls[t]=k; updata(k); updata(t); k=t;
return;
35 }
36 void ins(
int &k,
int val)
37 {
38 if (!
k)
39 {
40 k=++sz; size[k]=w[k]=
1; v[k]=sum[k]=val; rnd[k]=rand();
return ;
41 }
42 size[k]++; sum[k]+=
val;
43 if (val==v[k]) w[k]++
;
44 if (v[k]>val){ins(ls[k],val);
if (rnd[ls[k]]>
rnd[k]) rturn(k);}
45 if (v[k]<val){ins(rs[k],val);
if (rnd[rs[k]]>
rnd[k]) lturn(k);}
46 updata(k);
47 }
48 void del(
int &k,
int val)
49 {
50 if (!k)
return ;
51 if (v[k]==
val)
52 {
53 if (w[k])
54 {
55 w[k]--; size[k]--; sum[k]-=val;
return ;
56 }
57 if (ls[k]*rs[k]==
0) k=ls[k]+
rs[k];
58 else
59 {
60 if (rnd[ls[k]]>
rnd[rs[k]]) {rturn(k); del(k,val);}
61 else {lturn(k); del(k,val);}
62 }
63 }
64 else if (v[k]>val) {sum[k]-=val; size[k]--
; del(ls[k],val);}
65 else {sum[k]-=val; size[k]--
; del(rs[k],val);}
66 }
67 void init()
68 {
69 n=read(); k=read(); mmid=k/
2+
1; ans=
linf;
70 for(
int i=
1; i<=n; i++) a[i]=
read();
71 }
72 void find(
int k,
int rank)
73 {
74 if(!k)
return;
75 if(rank>size[ls[k]]&&rank<=size[ls[k]]+
w[k])
76 {
77 sum1+=(sum[ls[k]]+(rank-size[ls[k]]-
1)*
v[k]);
78 sum2+=(sum[rs[k]]+(size[ls[k]]+w[k]-rank)*
v[k]);
79 tmp=
v[k];
80 }
81 else if(rank<=
size[ls[k]])
82 {
83 sum2+=(v[k]*w[k]+
sum[rs[k]]);
84 find(ls[k],rank);
85 }
86 else
87 {
88 sum1+=(v[k]*w[k]+
sum[ls[k]]);
89 find(rs[k],rank-size[ls[k]]-
w[k]);
90 }
91 }
92 void getans()
93 {
94 sum1=sum2=
0;
95 find(root,mmid);
96 ll sum=(mmid-
1)*tmp-sum1+sum2-(k-mmid)*
tmp;
97 if(sum<ans)ans=
sum;
98 }
99 void solve()
100 {
101 root=
0;
102 for (
int i=
1; i<=k; i++
) ins(root,a[i]);
103 getans();
104 for (
int i=k+
1; i<=n; i++
)
105 {
106 del(root,a[i-
k]); ins(root,a[i]);
107 getans();
108 }
109 printf(
"%lld\n",ans);
110 }
111 int main()
112 {
113 init();
114 solve();
115 }
View Code
转载请注明原文地址: https://ju.6miu.com/read-1301013.html
