传送门
题目大意：有n个人围成一圈，每个人有ai个金币，每个人可以向相邻的人传金币。求出需要传递最少的金币数目使得每个人手中的金币数相等，数据保证金币总数时n的倍数。
解题思路：
我们设第i个人向前一个人传递xi个金币。并且我们可以求出每个人平均有多少个金币：M = sum/n;
那么： A[i] + x[i+1] - x[i] = M => x[i+1] = x[i] - (A[i] - M)
即：x[2] = x[1] - (A[1] -M)
x[3] = x[2] - (A[2] - M) => x[3] = x[1] -(A[1] -M) - (A[2] - M)
...
x[1] = x[1] - 0;
因此我们就转化成了 x[1] 到n个点的距离之和，每个点的距离ci = c[i-1] + (A[i] - M); 距离之和最小时 x1为这些点的中间。
AC代码：
#include <iostream> #include <cstdio> #include <algorithm> using namespace std; long long C[1000005]; int main() { int n; while(~scanf("%d", &n)) { long long sum = 0; for(int i=0; i<n; i++) { scanf("%lld", &C[i]); sum += C[i]; } sum /= n; C[0] = 0; C[1] = C[1] - sum; for(int i =2; i<n; i++) C[i] = C[i-1] + C[i] - sum; sort(C, C+n); long long ans =0; for(int i=0; i<n; i++) ans += abs(C[i] - C[n/2]); printf("%lld\n", ans); } return 0; }