BZOJ1045 HAOI2008糖块传递

BZOJ1045 HAOI2008糖果传递

很不错的题目啊。。

首先我们考虑一条链的情况，这个时候我们只需要构造出一个新的数列

也就是b[i]=a[i]-tot/n

然后绝对值加起来就可以了

但是环怎么做呢？

总不能枚举起点吧。。。。这样也太暴力了

我们可以假设答案就是从k开始传

那么这个时候就有abs(s[1]-s[k])+abs()+......+abs(a[n]-a[k])最小

看到这个想到什么呢？？？

距离！！

所以这个k显然是中位数

然后就没了

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define MAX 1000009
#define rep(i,j,k) for(int i=j;i<=k;i++)

using namespace std;

long long n,ans=0,b[MAX],a[MAX],tot,s[MAX];

int main()
{
	scanf("%lld",&n);
	rep(i,1,n)
		scanf("%lld",&a[i]),tot+=a[i];
	tot/=n;
	rep(i,1,n)
		b[i]=a[i]-tot;
	s[1]=b[1];
	rep(i,2,n)
		s[i]=s[i-1]+b[i];
	sort(s+1,s+1+n);
	int t=s[(n)>>1];
	rep(i,1,n)
		ans+=abs(s[i]-t);
	cout<<ans<<endl;
	return 0;
}