糖果传递

/*
  先表示出来，a1->a2,x1 为正数，a2->a3 ,x2为正数
  如果是 a2->a1, 则x1 为负数
  最终让所有的数字的值为 (a1+a2+...+an)/n,糖果数量相同
  最小化 |x1|+|x2|+...+|xn|

  a1 - x1 + xn = b
  a2 - x2 + x1 = b
  ....
  an - xn + xn-1 = b

  推导得到
  x1 = xn -(b-a1)
  x2 = x1 - (b-a2) = xn - (2*b - a1 - a2) 将 x1 带进来
  ...
  xn-1 = xn - ((n-1)*b - a1 - a2 - ...-an-1)
  xn =  xn - (n*b - a1 - a2 - ... an) = xn -0

  最终结果为 |xn -(b-a1)| + |xn - (2*b - a1 - a2)| + ... + |xn -0|
  等价于 = |x - c0| + |x - c1| + ...+ |x - cn-1|
  求这个的最小值，起始就是一个求x轴上的一个点到其余点的最小值： 货仓选址
  货仓选址，求中位数，带入求最小值

  证明，可以证明，一定存在某一个点，同时给左右两边的人糖果
  然后从这个点进行切割，形成一个线性的序列，分别赋值
  而且这些 xi 里面一定是部分是大于0 其他是小于 0 的，不可能同时为正或者负
  我们可以 xk >= 0, 立即给， xk <= 0 稍后给
 */

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int n;
LL s[N], c[N];
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%lld", &s[i]);
		s[i] += s[i - 1];
	}
	LL b = s[n] / n;
	int k = 0;
	for (int i = 1; i < n; i++)
		c[k++] = i * b - s[i];
	c[k++] = 0;
	// 求中位数
	// 对序列进行部分排序，找到 序列中第 n 小的元素
	// 将其放在正确的位置上
	// 确保该元素左边的所有元素都不大于它，右边的所有元素都不小于它
	nth_element(c, c + k / 2, c + k);
	LL res = 0;
	for (int i = 0; i < k; i++) {
		res += abs(c[i] - c[k / 2]);
	}
	printf("%lld\n", res);
	return 0;
}