第一步，当然是把数据减去平均数，然后我们可以得出一串正负不等的数列
我们用sum数组存该数列的前缀和。注意sum[ n ]=0
假设为链，那么可以得出答案为abs( sum[ 1 ] )+abs( sum[ 2 ] )+...+abs( sum[ n ] )
但是题目说的是环
我们设在第 k 个人处断开环成链。 那么答案为
abs( sum[ k+1 ] - sum[ k ] )+abs( sum[ k+2 ] - sum[ k ] )+...+abs( sum[ n ] - sum[ k ] )+abs( sum[ n ] - sum[ k ] + sum[ 1 ])+abs( sum[ n ] - sum[ k ] + sum[ 2 ])+...+abs( sum[ n ] - sum[ k ] + sum[ k ])
代入sum[ n ]=0后，得abs( sum[ k+1 ] - sum[ k ] )+abs( sum[ k+2 ] - sum[ k ] )+...+abs( sum[ n ] - sum[ k ] )+abs( sum[ 1 ] - sum[ k ] )+abs( sum[ 2 ] - sum[ k ] )+...+abs( sum[ k ] - sum[ k ] )
=abs( sum[1~n] - sum[k] )
我们把 sum[1~n] 扔到数轴上，发现问题变成：找出一个点，使它到其他点的距离最小。显然这个点是中位数。
end.
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cctype>
#include<algorithm>
using namespace std;
typedef long long ll;
inline ll Get(){
char c=getchar(); ll x=0;
while(!isdigit(c)) c=getchar();
while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=getchar();
return x;
}
ll ans,a[1000002],sum[1000002]; int n;
int main(){
scanf("%d",&n);
ll tot=0;
for(int i=1;i<=n;++i) a[i]=Get(),tot+=a[i];
tot/=n;
for(int i=1;i<=n;++i) a[i]-=tot,sum[i]=a[i]+sum[i-1]; //减平均数，求前缀和
sort(sum+1,sum+n+1);
ll mid=sum[(n+1)>>1]; //排序后找中位数
for(int i=1;i<=n;++i) ans+=abs(sum[i]-mid);
printf("%lld",ans);
return 0;
}