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
原题还要求输出结束状态时,每柱砖的高度.本题略去.
题解 据说有很多做法，有一些基于h[i]<=10^6
不过平衡树的做法还是比较容易想的
可以这样考虑
首先如果确定了一个区间，我们只需要求出区间中位数，可以枚举区间并在logn的时间内获得中位数
那么我们需要一种数据结构，支持插入删除，以及logn查询区间k大
平衡树可以实现，并且在获得中位数x时得出大/小等于x的数的个数以及和，就可以获得这个区间的最优值
也就是平衡树不仅要维护子树的大小，还要维护权值和
注意开longlong
代码
#include<cstdio> #include<cstring> #include<iostream> #include<cmath> #include<algorithm> #define ll long long #define linf 9223372036854775807LL int n,k,m,rt,sz; ll tmp; ll ans=linf,sum1,sum2; int a[100005]; int rnd[100005],size[100005],ls[100005],rs[100005],w[100005]; ll sum[100005],v[100005]; using namespace std; inline int read() { int x=0;char ch=getchar(); while(ch<'0'||ch>'9')ch=getchar(); while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x; } void update(int k) { size[k]=size[ls[k]]+size[rs[k]]+w[k]; sum[k]=sum[ls[k]]+sum[rs[k]]+v[k]*w[k]; } void lturn(int &k) { int t=rs[k];rs[k]=ls[t];ls[t]=k; update(k);update(t);k=t; } void rturn(int &k) { int t=ls[k];ls[k]=rs[t];rs[t]=k; update(k);update(t);k=t; } void insert(int &k,int x) { if (!k) { k=++sz; v[k]=sum[k]=x; size[k]=w[k]=1; rnd[k]=rand(); return; } size[k]++;sum[k]+=x; if (v[k]==x) w[k]++; else if (v[k]>x) { insert(ls[k],x); if (rnd[ls[k]]<rnd[k]) rturn(k); } else { insert(rs[k],x); if (rnd[rs[k]]<rnd[k]) lturn(k); } } void del(int &k,int x) { if (!k) return; if (v[k]==x) { if (w[k]>1){w[k]--;sum[k]-=x;size[k]--;return;} if (ls[k]*rs[k]==0) k=ls[k]+rs[k]; else if (rnd[ls[k]]<rnd[rs[k]]) rturn(k),del(k,x); else lturn(k),del(k,x); } else if (v[k]>x){size[k]--;sum[k]-=x;del(ls[k],x);} else{size[k]--;sum[k]-=x;del(rs[k],x);} } void find(int k,int rk) { if (!k) return; if (size[ls[k]]<rk&&size[ls[k]]+w[k]>=rk) { sum1+=(sum[ls[k]]+(rk-size[ls[k]]-1)*v[k]); sum2+=(sum[rs[k]]+(size[ls[k]]+w[k]-rk)*v[k]); tmp=v[k]; } else if (rk<=size[ls[k]]) { sum2+=(v[k]*w[k]+sum[rs[k]]); find(ls[k],rk); } else { sum1+=(v[k]*w[k]+sum[ls[k]]); find(rs[k],rk-size[ls[k]]-w[k]); } } void getans() { sum1=sum2=0; find(rt,m); ll sum=(m-1)*tmp-sum1+sum2-(k-m)*tmp; ans=min(sum,ans); } int main() { n=read();k=read();m=(k+1)>>1; for (int i=1;i<=n;i++) { a[i]=read(); } for (int i=1;i<=k;i++) insert(rt,a[i]); getans(); for (int i=k+1;i<=n;i++) { del(rt,a[i-k]); insert(rt,a[i]); getans(); } printf("%lld",ans); return 0; }