bzoj1045: [HAOI2008] 糖果传递（思维题）

　　首先每个人一定分到的糖果都是所有糖果的平均数ave。

　　设第i个人给i-1个人Xi个糖果，则有Ai-Xi+X(i+1)=ave。

　　则A1-X1+X2=ave,A2-X2+X3=ave,A3-X3+X4=ave。

　　X2=ave+X1-A1，A2-ave-X1+A1+X3=ave

　　X3=2ave+X1-A1-A2

　　设Bi=sigma(A(1~i-1))-(i-1)*ave

　　则答案为|Bi-X1|的和的最小值，求个中位数即可

#include<bits/stdc++.h>

#define ll long long

using namespace std;

const int maxn=;

int n,a[maxn];

ll sum,ave,b[maxn],mid,now,ans;

void read(int &k)

{

    int f=;k=;char c=getchar();

    while(c<''||c>'')c=='-'&&(f=-),c=getchar();

    while(c<=''&&c>='')k=k*+c-'',c=getchar();

    k*=f;

}

int main()

{

    read(n);

    for(int i=;i<=n;i++)read(a[i]),sum+=a[i];

    ave=sum/n;

    for(int i=;i<=n;i++)b[i]=b[i-]+a[i]-ave;

    sort(b+,b++n);

    mid=b[(n+)>>];

    for(int i=;i<=n;i++)

    ans+=abs(b[i]-mid);

    printf("%lld\n",ans);

}