自动搬运

查看原文

来自洛谷，原作者为

	communist Who Dare Wins !

搬运于2025-08-24 21:49:17，当前版本为作者最后更新于2018-09-18 17:28:46，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

容易想到，我们可以枚举所有长度为$k$的区间，算出把这段区间全部变成一个值的代价，对于所有区间取最小值即可

1，把这段区间变成几

可能能够猜出变成中位数，别人都是显然，只有我证了证（太弱了），给出一个简单的证明

对于一个序列$S$，设它的中位数为$x$

设序列中有$a$个数小于$x$，$b$个数大于$x$，$c$个数等于$x$

设将这段区间变为$x$的代价为$W$

考虑把这段区间变为$x+1$，新代价为$W+a+c-b$，因为

，所以新代价大于等于原代价

变为$x-1$同理

考虑两个中位数不同，选哪个

设序列中有$c$个数等于较小中位数$x$，较大中位数为$y$

考虑上式，两个中位数不同，对于满足$x+tmp<=y$，$a,b,c$是不变的，$a+c=b=k/2$，新代价等于旧代价

这样，我们知道了不仅两个中位数代价相同，而且两个中位数之间所有数代价相同

2，具体求代价

序列和与中位数乘序列长度作差？

直接作差不行，对于大于等于中位数的数求和减去中位数乘它们的个数

对于小于中位数的数，中位数乘它们的个数减去它们的和，两项求和即可

选择一个支持这些操作（中位数，小于和，插入删除）的数据结构吧，我选择了主席树

然后就是暴力打码了，不解释了

#include<iostream>
#include<cstdio>
#include<algorithm>
#define int long long
using namespace std;
const int maxn=1e5+10,maxv=1e6+1;
struct tree{
    int v,ls,rs,sum;
}a[25*maxv];
int n,k,rt[maxn],cnt,v[maxn],ans=1e15,p,all,ave;
void insert(int pre,int cur,int p,int l,int r)
{
    if(l==r)
    {
        a[cur].v=a[pre].v+1;
        a[cur].sum=a[pre].sum+l;
        return;
    }
    int m=l+r>>1;
    if(p<=m)
    {
        a[cur].ls=++cnt;
        a[cur].rs=a[pre].rs;
        insert(a[pre].ls,a[cur].ls,p,l,m);
    }
    else
    {
        a[cur].rs=++cnt;
        a[cur].ls=a[pre].ls;
        insert(a[pre].rs,a[cur].rs,p,m+1,r);
    }
    a[cur].v=a[a[cur].ls].v+a[a[cur].rs].v;
    a[cur].sum=a[a[cur].ls].sum+a[a[cur].rs].sum;
}
int kth(int x,int y,int k,int l,int r)
{
    if(l==r)
        return l;
    int m=l+r>>1,num=a[a[y].ls].v-a[a[x].ls].v;
    if(num>=k)
        return kth(a[x].ls,a[y].ls,k,l,m);
    else
        return kth(a[x].rs,a[y].rs,k-num,m+1,r);
}
int sum(int x,int y,int k,int l,int r)
{
    if(l==r)
        return min(k,a[y].v-a[x].v)*l;
	int m=l+r>>1,num=a[a[y].ls].v-a[a[x].ls].v;
	//printf("%d %d %d\n",m,num,k);
    if(num>=k)
    	return sum(a[x].ls,a[y].ls,k,l,m);
    else
        return a[a[y].ls].sum-a[a[x].ls].sum+sum(a[x].rs,a[y].rs,k-num,m+1,r);
}
signed main()
{
    scanf("%lld%lld",&n,&k);
    for(int i=1;i<k;i++)
    {
    	scanf("%lld",&v[i]);
        rt[i]=++cnt,all+=v[i];
        insert(rt[i-1],rt[i],v[i],0,1e6);
	}
    for(int i=k;i<=n;i++)
    {
        scanf("%lld",&v[i]);
        rt[i]=++cnt,all+=v[i]-v[i-k];
        insert(rt[i-1],rt[i],v[i],0,1e6);
        int pos=k+1>>1,tmp=kth(rt[i-k],rt[i],pos,0,1e6),res=sum(rt[i-k],rt[i],pos,0,1e6);
        res=all-2*res-(k-pos)*tmp+pos*tmp;
        if(res<ans)
        {
        	ans=res;
        	p=i,ave=tmp;
		}
    }
    printf("%lld\n",ans);
    for(int i=1;i<=n;i++)
    	if(p<i+k&&p>=i)
    		printf("%lld\n",ave);
    	else
    		printf("%lld\n",v[i]);
    return 0;
}