自动搬运

查看原文

来自洛谷，原作者为

	翟翟 我在黄昏垂钓太阳。试图拉起我堕落的人生。

搬运于2025-08-24 22:14:38，当前版本为作者最后更新于2023-07-10 19:43:58，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

目标是让每个人的金币数变为 $\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_3=X_2+\overline{a}-a_2=X_1+\overline{a}-a_1+\overline{a}-a_2$；

易得 $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;
}