对于每个人和平均值ave相比，要么少要么多，此时引用一个x[i]表示i人和i - 1之间的交易,正负可表示传递方向，得出公式： a[i] + x[i] + x[i + 1] = ave (其中x[i]有正有负)后面将设定大于0，表示当前i人向左传递数量

A1-X1+X2=ave -> X2=ave-A1+X1 = X1-C1 (假设C1=A1-ave)这里引入一个c
A2-X2+X3=ave -> X3=ave-A2+X2=2ave-A1-A2+X1=X1-C2 (即C2=A1+A2-2ave=A2+C1-ave)
我们希望Xi的绝对值之和尽量小，即|X1| + |X1-C1| + |X1-C2| + ……+ |X1-Cn-1|要尽量小
所以找一个x1满足这个条件。

ac code:

#include<bits/stdc++.h>
typedef long long LL;
using namespace std;
const int N = 1e6 + 10;
int n;
LL a[N],su,ave,ans;
LL c[N];
int main ()
{
	cin >> n;
	for(int i = 1;i <= n;++ i)
	{
		cin >> a[i];
		su += a[i];
	}
	ave = su / n;
	for(int i = 1;i <= n;++ i)
	{
		c[i] = c[i - 1] + ave - a[i - 1];
	}
	sort(c + 1,c + 1 + n);
	LL m = c[(n + 1) / 2];
	for(int i = 1;i <= n;++ i)
	{
		ans += abs(m - c[i]);
	}
	cout << ans;
	return 0;
}