分析
通过小学数学我们可以知道对于k个数，我们取它们的中位数x时可以使答案最优。所以我们枚举每一个连续的长度为k的区间，用treap维护，求出所有数都变成x的花费。注意在这里treap还需要记录它的子树的值的和以便最后计算答案的时候使用。具体实现见代码。记得开long long。
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cctype>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<ctime>
#include<vector>
#include<set>
#include<map>
#include<stack>
using namespace std;
const long long inf = 1e13+7;
long long siz[110000],sum[110000],son[2][110000],a[110000],rd[110000];
long long n,m,cnt,root,b[110000];
inline void up(long long x){
siz[x]=siz[son[0][x]]+siz[son[1][x]]+1;
sum[x]=sum[son[0][x]]+sum[son[1][x]]+a[x];
}
inline void rot(long long &rt,long long p){
long long t=son[p][rt];
son[p][rt]=son[!p][t],son[!p][t]=rt;up(rt),up(t);rt=t;
}
inline void ins(long long &rt,long long x){
if(!rt){rt=++cnt;sum[rt]=x;siz[rt]=1;a[rt]=x;rd[rt]=rand();return;}
siz[rt]++;
sum[rt]+=x;
if(x<=a[rt]){ins(son[0][rt],x);if(rd[son[0][rt]]<rd[rt])rot(rt,0);}
else {ins(son[1][rt],x);if(rd[son[1][rt]]<rd[rt])rot(rt,1);}
}
inline void del(long long &rt,long long x){
if(a[rt]==x){
if(!son[0][rt]||!son[1][rt]){rt=son[0][rt]+son[1][rt];return;}
if(rd[son[0][rt]]>rd[son[1][rt]]){rot(rt,1);del(son[0][rt],x);}
else {rot(rt,0);del(son[1][rt],x);}
up(rt);return;
}
if(a[rt]>x)del(son[0][rt],x);else del(son[1][rt],x);up(rt);
}
long long res1,res2,s1,s2;
inline long long fk(long long rt,long long k){
if(siz[son[0][rt]]==k-1){
s1+=siz[son[0][rt]],s2+=siz[son[1][rt]];
res1+=sum[son[0][rt]],res2+=sum[son[1][rt]];return a[rt];
}
if(siz[son[0][rt]]>=k){
s2+=siz[son[1][rt]]+1,res2+=sum[son[1][rt]]+a[rt];
return fk(son[0][rt],k);
}else {
s1+=siz[son[0][rt]]+1,res1+=sum[son[0][rt]]+a[rt];
return fk(son[1][rt],k-1-siz[son[0][rt]]);
}
}
inline long long getans(){
res1=res2=s1=s2=0;
long long x=fk(root,(m-1)/2+1);
return res2-s2*x+s1*x-res1;
}
int main(){
srand(time(0)+20021023);
long long i,j,k,ans=inf;
scanf("%lld%lld",&n,&m);
for(i=1;i<=n;i++)scanf("%lld",&b[i]);
for(i=1;i<m;i++)ins(root,b[i]);
for(i=0;i+m<=n;i++){
ins(root,b[i+m]);
if(i)del(root,b[i]);
ans=min(ans,getans());
}
printf("%lld
",ans);
return 0;
}