Description：

有 $n$ 个小朋友坐成一圈，每人有 $a_i$ 个糖果。每人只能给左右两人传递糖果。每人每次传递一个糖果代价为 $1$ 。

求使所有人获得均等糖果的最小代价。

$1\le n \le 1000000$

Solution：

设每个人收到左边的 $l_i$ 个，右边的 $r_i$ 个，负数代表给，设 $k=\frac{\sum a_k}n$ 则有 $a_i+l_i+r_i=k$

发现 $l_i=-r_{i-1}$ ，于是有 $r_i-r_{i-1}=k-a_i$ ，但发现有一组方程是线性相关的，相当于知道了一个差分数组，随便设一个为零，就变成了给数轴上的一些点，求一个点到所有点的距离之和最小，答案就是中位数。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n;

typedef long long ll;

#define MAXN 1000010

ll a[MAXN],diff[MAXN],sum = 0;

ll r[MAXN];

int main()

{

	scanf("%d",&n);

	for(int i = 1;i <= n;++i)scanf("%lld",&a[i]);

	for(int i = 1;i <= n;++i)sum += a[i];

	sum /= (ll)n;

	for(int i = 2;i <= n;++i)diff[i] = sum - a[i];

	for(int i = 2;i <= n;++i)r[i] = r[i - 1] + diff[i];

	sort(r + 1,r + 1 + n);

	ll ans = 0;

	for(int i = 1;i <= n;++i)

	{

		ans += abs(r[i] - r[(n + 1) / 2]);

	}

	cout << ans << endl;

	return 0;

}