P5817 [CQOI2011] 分金币
翟翟
·
·
题解
目标是让每个人的金币数变为 \large\overline{a}=\frac{\sum\limits_{i=1}^n a_i}{n}。
记 X_i 为编号为 i 的人向其左边的人给的金币数量，负数反之。则 ans=\large\sum\limits_{i=1}^n |X_i|。
我们发现传递后第 i 个人金币数为 a_i+X_{i+1}-X_i=\overline{a}。
所以 X_i=X_{i-1}+\overline{a}-a_{i-1}。
则 X_2=X_1+\overline{a}-a_1；
易得 $X_i=X_1+(i-1)\times\overline{a}-\large\sum\limits_{j=1}^{i-1}a_j$。
记 $C_i=\large\sum\limits_{j=1}^i a_j-i\times\overline{a}=\large\sum\limits_{j=1}^i(a_j-\overline{a})$，
则 $X_i=X_1-C_{i-1}$，$C$ 数组可求前缀和得出。
则 $ans=\large\sum\limits_{i=1}^n|X_1-C_{i-1}|$，类似在数轴上有 $n$ 个点，找到一个与所有点距离和最小的点。对 $C$ 数组排序，若 $n$ 为奇数，$X_i$ 取 $\large C_{\frac{n+1}{2}}$；若 $n$ 为偶数，$X_1$ 取 $\large C_{\frac{n}{2}-1}$ 到 $\large C_{\frac{n}{2}}$ 的数都可以，所以我们取 $\large X_1=C_{\lfloor{\frac{n+1}{2}}\rfloor}$ 便可以求出 $ans$ 的最小值。
时间复杂度 $\large\mathcal{O}(n \log n)$，瓶颈在于排序。
## Code
```
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+1;
int n,a[N],sum,mid,s[N];
long long ans;
int main(){
scanf("%d",&n);
for(int i=1;i<=n;++i){
scanf("%d",a+i);
sum+=a[i];
}
sum/=n;
for(int i=1;i<n;++i)
s[i]=s[i-1]+a[i]-sum;
sort(s,s+n);
mid=s[n>>1];
for(int i=0;i<n;++i)
ans+=abs(s[i]-mid);
printf("%lld\n",ans);
return 0;
}
```