【BZOJ1045】[HAOI2008] 糖果传递
Description
有n个小朋友坐成一圈，每人有ai个糖果。每人只能给左右两人传递糖果。每人每次传递一个糖果代价为1。
Input
第一行一个正整数n<=987654321，表示小朋友的个数．接下来n行，每行一个整数ai，表示第i个小朋友得到的
糖果的颗数．
Output
求使所有人获得均等糖果的最小代价。
Sample Input
4
1
2
5
4
1
2
5
4
Sample Output
4
题解：面对环上的问题我们仍然考虑把环拆开
我们先不考虑n—1的传递，只考虑1—2—3。。—n的传递，此时有无脑贪心：
第i人向第i-1个人传递s[i-1]-(i-1)*ave个糖果，代价是s[i-1]-(i-1)*ave的绝对值，其中s是前缀和，ave是平均数
当1能向n传递时，假设传递的个数是x，则以后的所有i向i-1传递的数量都会减去x，但由于要取绝对值，所以如果s[i-1]-(i-1)*ave-x为正，则总代价会-x，若为负，则总代价会+x，那么最优情况肯定是是s[i-1]-(i-1)*ave-x中正数和负数的个数相等，即x取s[i-1]-(i-1)*ave的中位数（别忘了把0加上）
注意开long long
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
long long a[1000010],b[1000010];
long long n,ans,tot;
int main()
{
scanf("%lld",&n);
int i;
for(i=1;i<=n;i++) scanf("%lld",&a[i]),tot+=a[i];
tot/=n;
for(i=2;i<=n;i++) b[i]=b[i-1]+a[i]-tot;
sort(b+1,b+n+1);
for(i=1;i<=n;i++) ans+=abs(b[i]-b[n+1>>1]);
printf("%lld",ans);
return 0;
}