https://www.acwing.com/problem/content/description/124/
参考题解：https://www.acwing.com/solution/acwing/content/955/
题意：n个小朋友坐成环形，每个小朋友有a[i]颗糖，可以向左右传递，求最小的传递代价。
设x[i]为第i个小朋友给他左边的小朋友的糖果的数量，负数也可以。
那么答案就是：
[sumlimits_{i=1}^{n}|x[i]|
]
根据题意可以列出方程：
[avg=a[i]-x[i]+x[i+1]
]
这n个方程互相制约，所以是关于x[1]的单变量函数。
然后假如设$$c[i]=a[i]-avg$$
就有
[x[2]=avg-a[1]-x[1]=x[1]-c[1]
]
[x[3]=avg-a[2]-x[2]=x[2]-c[2]=x[1]-c[1]-c[2]
]
[x[4]=x[1]-c[1]-c[2]-c[3]
]
所以假如设$$s[n]=sumlimits_{i=1}^{n}c[i-1]$$
就变成(sumlimits_{i=1}^{n}|x[i]|)的最小值，
也就是(sumlimits_{i=1}^{n}|x[1]-s[i]|)，变成货仓选址问题。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
int a[2000005];
ll s[2000005];
ll calc() {
ll sum = 0;
for(int i = 1; i <= n; ++i)
sum += a[i];
int mean = sum / n;
for(int i = 1; i <= n; ++i) {
s[i] = s[i - 1] + a[i] - mean;
}
sort(s + 1, s + 1 + n);
ll res = 0;
int m = s[(n + 1) >> 1];
for(int i = 1; i <= n; ++i)
res += abs(s[i] - m);
return res;
}
int main() {
#ifdef Yinku
freopen("Yinku.in", "r", stdin);
#endif // Yinku
scanf("%d", &n);
for(int i = 1; i <= n; ++i)
scanf("%d", &a[i]);
printf("%lld
", calc());
}