http://www.zybbs.org/JudgeOnline/problem.php?id=1045

555……现在我只能做做傻题了，好桑心……

假设平均数是x，且a1给an了k个（k<0说明是an给a1了-k个），那么总代价就可以算出来：

令bi=sum(a1..i)-ix，则总代价=sum|bi-k|。易知k为中位数时此值最小。问题转化为求中位数……或者直接qsort排序也行。

然后我苦逼地改我的快速k大……最后发现是pi!=p||pj!=p而不是pi!=p&&pj!=p……这里当时还想了半天……我不会快排了T^T

#include <stdio.h>
#include <stdlib.h>
int n,a[1000000],z;
char str[10000000],*p=str;
long long avr,sum;
inline getint(){
	int re=0;
	while(*p<'0'||*p>'9')p++;
	while(*p>='0'&&*p<='9')re=re*10+*p++-48;
	return re;
}void solve(a,j,k)int*a,j,k;{
	int p=j>>1,pi=0,pj=j-1,t;
	while(pi!=p||pj!=p){
		while(a[pi]<=a[p]&&pi<p)pi++;
		if(pi!=p){t=a[p];a[p]=a[pi];a[p=pi]=t;}
		while(a[pj]>=a[p]&&pj>p)pj--;
		if(pj!=p){t=a[p];a[p]=a[pj];a[p=pj]=t;}
	}if(p>k)solve(a,p,k);
	else if(p<k)solve(a+p+1,j-p-1,k-p-1);
}main(){
	int i=-1;fread(p,1,10000000,stdin);
	for(n=getint();++i!=n;)avr+=a[i]=getint();
	avr/=n;
	for(i=-1;++i!=n;a[i]=sum-a[i]+avr)sum+=a[i]-avr;
	sum=0;solve(a,n,n>>1);z=a[n>>1];
	for(i=-1;++i!=n;)sum+=abs(z-a[i]);
	return printf("%lld\n",sum),0;
}

• inline
• block