Description
有n个小朋友坐成一圈，每人有ai个糖果。每人只能给左右两人传递糖果。每人每次传递一个糖果代价为1。
Input
小朋友个数n 下面n行 ai
Output
求使所有人获得均等糖果的最小代价。
Sample Input
4
1
2
5
4
Sample Output
4
HINT
数据规模
30% n<=1000
有n个小朋友坐成一圈，每人有ai个糖果。每人只能给左右两人传递糖果。每人每次传递一个糖果代价为1。
Input
小朋友个数n 下面n行 ai
Output
求使所有人获得均等糖果的最小代价。
Sample Input
4
1
2
5
4
Sample Output
4
HINT
数据规模
30% n<=1000
100% n<=100000
解析
首先我们可以把a数组里面所有的数和平均数进行一次求差得到一个b数组
前后相加后便得到一个s数组
因为本题是一个环，那么需要求的答案便是|s[1]-s[k]|+|s[2]-s[k]|+|s[3]-s[k]|+...+|s[n-1]-s[k]|+|s[n]-s[k]|（其中k代表一个点，这个点作为一个中转站）
所以要求的最小值，s[k]就必须是中位数！
完整代码
/**************************************************************Problem: 1045User: chenyushuo2012Language: C++Result: AcceptedTime:2808 msMemory:17992 kb
****************************************************************/#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;
long long a[1100000], s[1100000], n;
int main (){long long i, j, k, ave;scanf ( "%d", &n );ave = 0;for ( i = 1; i <= n; i ++ ){ scanf ( "%lld", &a[i] ); ave += a[i]; }ave /= n;for ( i = 1; i <= n; i ++ ){a[i] -= ave;s[i] = s[i-1] + a[i];}sort ( s+1, s+n+1 );k = s[n/2];long long sum = 0;for ( i = 1; i <= n; i ++ ) sum += abs (s[i]-k);printf ( "%lld\n", sum );return 0;
}