分金币
【问题描述】
圆桌上坐着n个人，每人有一定数量的金币，金币总数能被n整除。每个人可以给他左右相邻的人一些金币，最终使得每个人的金币数目相等。你的任务是求出被转手的金币数量的最小值。
【输入格式】
第一行为整数n（n>=3），以下n行每行一个正整数，按逆时针顺序给出每个人拥有的金币数。
【输出格式】
输出被转手金币数量的最小值。
【样例输入】
4
1
2
5
4
【样例输出】
4
【样例说明】
设四个人编号为1,2,3,4。第3个人给第2个人2个金币（变成1,4,3,4），第2个人和第4个人分别给第1个人1个金币。
【数据范围】
N<=<=100000,总金币数<=10^9
题解：
设a[i]为第i个人的初始金币数，
设p为a数组的平均数，
设c[i]为第i个人从第i-1个人拿到的金币数，那么：
将上列等式经过数学转换后可得:
C[i] = c[n] - (a[i] +···+ a[n]) + (n - i + 1)p，
答案即为
Ans = |c[1]| +···+ |c[n]|，
那么设
e[i] = - (a[i] +···+ a[n]) + (n - i + 1)p;，
因为a数组与p已知，所以e[i]已知，
那么答案
Ans = |e[1] - (-c[n])| +···+|e[n] - (-c[n])|，
观察式子可知答案即为在数轴上-c[n]分别到e[1] ~ e[n]的距离之和，
要使答案最小，则-c[n]取e数组的中位数时最优，最后统计答案。
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
using namespace std;
inline int Get()
{
int x = ;
char c = getchar();
while('' > c || c > '') c = getchar();
while('' <= c && c <= '')
{
x = (x << ) + (x << ) + c - '';
c = getchar();
}
return x;
}
int n;
long long cc;
long long sum;
long long ans;
long long c[];
long long a[];
int main()
{
n = Get();
for(int i = ; i <= n; ++i)
{
a[i] = Get();
sum += a[i];
}
sum /= n;
a[] = a[n];
for(int i = ; i <= n; ++i)
c[i] = c[i - ] + a[i - ] - sum;
sort(c + , c + + n);
cc = -c[(n >> ) + ];
for(int i = ; i <= n; ++i) ans += abs(c[i] + cc);
printf("%lld", ans);
fclose(stdin), fclose(stdout);
}