题目描述

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

题目分析

最优情况是高度为区间中位数 (我不会证)
那么我们每枚举k个数 求出中位数 利用中位数求出答案 最后取最小值即可
令
为小于等于中位数的数的个数
为大于等于中位数的数的个数
为小于等于中位数的数的和
为大于等于中位数的数的和
为中位数

这里使用动态开点权值线段树来求解中位数

#include <cstdio>
#include <cstring>
#include <set>
#include <map>
#include <vector>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int n,k;
struct your
{
    int x,y,size;
    long long sum;
}a[1000100*4];
int val[100010];
void build(int dx,int dy,int num)
{
    a[num].x=dx,a[num].y=dy;
    if(dx==dy) return ;
    int mid=(a[num].x+a[num].y)>>1;
    build(dx,mid,num<<1),build(mid+1,dy,num<<1|1);
}
void update(int dx,int num,int c)
{
    if(a[num].x==dx&&a[num].y==dx)
    {
        a[num].size+=c;
        a[num].sum=(long long) a[num].size*(dx-1);
        return ;
    }
    int mid=(a[num].x+a[num].y)>>1;
    if(dx>mid) update(dx,num<<1|1,c);
    else update(dx,num<<1,c);
    a[num].size=a[num<<1].size+a[num<<1|1].size;
    a[num].sum=a[num<<1].sum+a[num<<1|1].sum;
}
int getv(int dx,int num)
{
    if(a[num].x==a[num].y) return a[num].x;
    if(dx<=a[num<<1].size) return getv(dx,num<<1);
    return getv(dx-a[num<<1].size,num<<1|1);
}
int getl(int dx,int num)
{
    if(dx>=a[num].y) return a[num].size;
    if(dx<=a[num<<1].y) return getl(dx,num<<1);
    else return a[num<<1].size+getl(dx,num<<1|1);
}
long long gets(int dx,int num)
{
    if(dx>=a[num].y) return a[num].sum;
    if(dx<=a[num<<1].y) return gets(dx,num<<1);
    else return a[num<<1].sum+gets(dx,num<<1|1);
}
long long value[100100],ans=100000000000000;
int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++) scanf("%d",&val[i]);
    build(1,1000010,1);
    for(int i=1;i<=k;i++) update(val[i]+1,1,1);
    for(int i=1;i<=n;i++) value[i]=(long long)value[i-1]+val[i];
    for(int i=k;i<=n;i++)
    {
        int tmp=getv((k+1)>>1,1);
        int lsize,rsize;
        long long lsum,rsum;
        lsize=getl(tmp,1),rsize=k-lsize;
        lsum=gets(tmp,1),rsum=value[i]-value[i-k]-lsum;
        tmp--;
        long long nmp=(long long) tmp*lsize-lsum+rsum-(long long) tmp*rsize;
        ans=min(ans,nmp);
        if(i==n) continue;
        update(val[i-k+1]+1,1,-1);
        update(val[i+1]+1,1,1);
    }
    printf("%lld",ans);
    return 0;
}