非常好的一道数学题。
题目分析
（参考刘汝佳《算法竞赛入门经典 \(\cdot\) 训练指南》）
本身看起来很复杂。不要急，我们慢慢分析。
首先，每个人最终的金币数是可以计算出来的，即总金币数去除以总人数，我们设这个数等于\(M\)。
假设一共有 \(n\) 个人，编号为 \(1\)，\(2\)，\(3\)，\(4\)，\(\cdots\)。设每个人刚开始拥有的金币数为 \(A_i\)，\(x_i\) 表示第 \(i\) 个人给其上一个人的金币数（\(x_1\) 表示给 \(n\) 的金币数）。那么对于编号 \(1\)，经转手后的金币数就等于 \(M=A_1-x_1+x_2\)，同理：\(M=A_2-x_2+x_3,M=A_3-x_3+x_4\cdots\)。最终我们就可以获得第 \(n\) 个式子 \(M=A_n-x_n+x_1\)，那我们是不是就可以解方程组了呢？很遗憾，最后一个方程是可以通过前 \(n-1\) 个方程推导出来的，故只有前 \(n-1\) 个方程是有用的。
尽管无法直接求解，我们还是可以用 \(x_1\) 表示其他的 \(x_i\)，进而转化为单变量的极值问题。
对于第 \(1\) 个人，可以得到 \(x_2=x_1+M-A_1\)。
对于第 \(2\) 个人，可以得到 \(x_3=x_2+M-A_2=x_1+M-A_2+M-A_1\)。
对于第 \(3\) 个人，可以得到 \(x_4=x_3+M-A_3=x_1+M-A_3+M-A_2+M-A_1\)。
\(\cdots\)
所以对于第 \(n\) 个人，有 \(x_n=x_1+nM-(\sum_{i=1}^nA_i)\)。
最后，我们要求解的是转手金币数的最小值，也就是 \(\min\{\sum_{i=1}^n|x_i|\}\)，所以这个时候我们令 \(C_i=(\sum_{i=1}^nA_i)-i\cdot M\)，这样，我们要求解的式子就变成 \(\min\{|x_1|+|x_1-C_1|+|x_2-C_2|+\cdots +|x_n-C_n|\}\)。由于两个值的差的绝对值的几何意义是二者的距离，所以我们把求最小值这个问题放在数轴上来解决，问题也转成求 \(x_1\) 到各个 \(C_i\) 的距离之和的最小值。
假设我们的红圈（\(x_1\)）向右微微移动了 \(d\) 个单位，那么对于左边就增加了 \(2d\) 的距离，对于右边减少了 \(4d\) 的距离，故减少了 \(2d\) 的距离。所以每次只要我们向蓝圈更多的一边去移动，就会对答案产生贡献，进而推出当红圈两边的蓝圈数相等，即处于中位数时，可以获得最小值。之后我们将 \(C_i\) 从小到大来排序，然后统计答案即可。
对于 \(A_i\)，我们没有任何必要保存，具体实现请看代码：
点击查看代码
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define ll long long
using namespace std;
ll M,sum;
int n;
ll C[1000005];
inline ll re(){
register ll k=0,f=1ll;
register char c=getchar();
while(!isdigit(c)){
if(c=='-') f=-1ll;
c=getchar();
}
while(isdigit(c)){
k=k*10ll+(c^48ll);
c=getchar();
}
return 1ll*k*f;
}
void wr(ll x){
if(x<0){
x=~x+1;
putchar('-');
}
if(x>9) wr(x/10ll);
putchar(x%10ll^48ll);
}
signed main(){
while(scanf("%d",&n)!=EOF){
for(int i=1;i<=n;++i) C[i]=0;
for(int i=1;i<=n;++i){
ll x=re();
C[i]=x+C[i-1];
}
M=C[n]/n;
for(int i=1;i<=n;++i) C[i]-=i*M;
sort(C+1,C+1+n);
ll x=C[(n+1)/2],ans=0;
for(int i=1;i<=n;++i)
ans+=abs(x-C[i]);
wr(ans);
putchar('\n');
}
return 0;
}