【BZOJ1112】[POI2008]砖块Klo
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
3
9
2
3
1
Sample Output
2
HINT
原题还要求输出结束状态时,每柱砖的高度.本题略去.
题解：我们先只考虑一段区间，如果我们想花最小的费用使所有权值相等，那么一定是将他们全变成这段区间的中位数，那么我们只需要从左往右平移这段区间，那么就将问题转变成了动态求某段区间内的中位数，用Treap完全可以搞定。
那么如何得到答案呢？我们可以将答案表示成这样：
ans=（所有比mid大的元素的和 - mid * 比mid大的元素的个数）+（mid * 比mid小的元素的个数 - 所有比mid小的元素的和）
这个我们可以在递归求mid的时候顺便就求出来，具体细节什么的还是自己YY一下吧
别忘了开long long
#include <cstdio>
#include <cstring>
#include <iostream>
#include <cstdlib>
using namespace std;
typedef long long ll;
const int maxn=100010;
int n,m,tot,root,mid;
ll ans,minn;
int k[maxn],ch[maxn][2];
ll h[maxn],v[maxn],siz[maxn],s[maxn],sum[maxn],cnt[maxn];
void pushup(int x)
{
siz[x]=siz[ch[x][0]]+siz[ch[x][1]]+cnt[x];
sum[x]=sum[ch[x][0]]+sum[ch[x][1]]+v[x]*cnt[x];
}
void rotate(int &x,int d)
{
int y=ch[x][d];
ch[x][d]=ch[y][d^1],ch[y][d^1]=x;
pushup(x),pushup(y);
x=y;
}
void insert(int &x,ll y)
{
if(!x)
{
x=++tot,sum[x]=v[x]=y,siz[x]=cnt[x]=1,k[x]=rand();
return ;
}
siz[x]++;
if(v[x]==y)
{
cnt[x]++,sum[x]+=y;
return ;
}
int d=(y>v[x]);
insert(ch[x][d],y);
if(k[ch[x][d]]>k[x]) rotate(x,d);
pushup(x);
}
void del(int &x,ll y)
{
if(v[x]==y)
{
if(cnt[x]>1)
{
cnt[x]--,siz[x]--,sum[x]-=y;
return ;
}
if(ch[x][0]*ch[x][1]==0) x=(ch[x][0]^ch[x][1]);
else rotate(x,(k[ch[x][0]]<k[ch[x][1]])),del(x,y);
return;
}
siz[x]--,sum[x]-=y;
if(v[x]>y) del(ch[x][0],y);
else del(ch[x][1],y);
}
void query(int x,int y)
{
if(siz[ch[x][0]]>=y) ans+=sum[ch[x][1]]+v[x]*cnt[x],query(ch[x][0],y);
else if(siz[ch[x][0]]+cnt[x]<y) ans-=sum[ch[x][0]]+v[x]*cnt[x],query(ch[x][1],y-siz[ch[x][0]]-cnt[x]);
else ans+=sum[ch[x][1]]-sum[ch[x][0]]+v[x]*(2*siz[ch[x][0]]+cnt[x]-2*y+(m&1));
}
int main()
{
srand(233333);
int i;
scanf("%d%d",&n,&m);
for(i=1;i<m;i++) scanf("%lld",&h[i]),s[i]=s[i-1]+h[i],insert(root,h[i]);
minn=1ll<<60;
for(;i<=n;i++)
{
scanf("%d",&h[i]),s[i]=s[i-1]+h[i],insert(root,h[i]);
if(i>m) del(root,h[i-m]);
ans=0,query(root,m+1>>1);
minn=min(minn,ans);
}
printf("%lld",minn);
return 0;
}