我们的目标是令 $A_i$ 变为：

$\frac{1}{n} \sum_{i=1}^{n}A_i$

我们不妨设：

$W_i$为相邻两个牌堆之间的传递数（单向，负数表示反向）

则

$A_i-W_i+W_{i-1}=X$

联立后不难注意到

$W_i=(i-1)x-(\sum_{j=1}^{i-1}A_i)+W_1$

那么我们的目标其实就是最小化：

$\sum_{i=1}^{n}W_i$

然而，前文提到了

W_i为单向，负数表示反向

也就是说，实际上，我们应该最小化：

$\sum_{i=1}^{n} \left | W_i \right |$

即

$ans=\sum_{i=1}^{n}\left |\frac{i-1}{n} \sum_{j=1}^{n}A_i -(\sum_{j=1}^{i-1}A_i)+W_1\right |$

换而言之

货仓选址

那这个题就做完了

code：

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){
	int x=0,f=1;
	char ch=getchar();
	while(!isdigit(ch)){
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(isdigit(ch)){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x*f;
}
inline void write(int x){
	if(x<0)putchar('-'),x=-x;
	if(x>9)write(x/10);
	putchar(x%10+48);
}
const int N=1e7+10;
int a[N];
int sum[N];
int x;
int ans;
int n;
signed main(){
	n=read();
	for(int i=1;i<=n;i++)a[i]=read(),x+=a[i];
	x/=n;
	for(int i=1;i<=n;i++)sum[i]=sum[i-1]+x-a[i-1];
	sort(sum+1,sum+n+1);
	for(int i=1;i<=n;i++)ans+=abs(sum[n/2+1]-sum[i]);
	write(ans);	
	return 0;
}

٩(๑>◡<๑)۶

假设只能往右传递，贡献值为 t （若 t < 0 则表示向左传递）

第 1 个人往右传递的纸牌数为 $t_1$

第 2 个人往右传递的纸牌数为 $t_2$

……

第 n 个人往右传递的纸牌数为 $t_n$

则：

$a_1 + t_n - t_1$ = ave

$a_2 + t_1 - t_2$ = ave

……

$a_i + t_{i-1} - t_i$ = ave

……

$a_n + t_{n-1} - t_n$ = ave

===>

$t_1$ = $t_n + a_1$ - ave

$t_2$ = $t_n + a_1 + a_2$ - 2*ave

……

$t_i$ = $t_n + a_1 + a_2 + …… + a_{i}$ - i*ave

……

$t_n$ = $t_n + a_1 + a_2 + …… + a_{n}$ - n*ave

设 $x_i = i*ave - sum_{k=1}^{i} a_k$

则：

$sum_{i=1}^{n}|t_i| = |t_n-x_1| + |t_n-x_2| + …… + |t_n-x_n|$

求该式最小值？

中位数！

第一眼看过去是一个经典的模型：环形均分纸牌。

结论：

对于环形均分纸牌问题，将 $A_i - 最后每一个人将会得到的牌的数量$ ，使得目标是将 $A_i$ 全设置为 0 。然后令 $S_i$ 为 $A_i$ 的前缀和，所需最少步数即为

$$\min_{k\in[1,n]} \sum\limits_{i=1}\limits^{n} |S_i-S_k| $$

---

$证明：$

先考虑不是环形的情况：

若 $A_1>0$ ，则第一个人要给第二个人 $A_1$ 张牌，$A_2$ 加上 $A_1$

若 $A_1<0$ ，则第二个人要给第一个人 $-A_1$ 张牌, $A_2$ 减去 $-A_1$，负负得正， $A_2$ 还是加上 $A_i$

按照同样的方法，依次考虑每一个人，答案即为 $\sum\limits_{i=1}\limits^{n} |S_i|$

再考虑是环形的情况：

显然，最优解中一定会有两个人不交换纸牌，因此可以枚举一个断点 $k$ ，从那里短环成链

便有了一个表格：

纸牌数	前缀和（以 $k$ 为起点）
$A_{k+1}$	$S_{k+1}-S_{k}$
$A_{k+2}$	$S_{k+2}-S_{k}$
$A_{k+3}$	$S_{k+3}-S_{k}$
$...$	$$...$$
$A_{N}$	$S_{N}-S_{k}$
$A_{1}$	$S_{1}+S_{N}-S_{k}$
$A_{2}$	$S_{2}+S_{N}-S_{k}$
$...$	$$...$$
$A_{k}$	$S_{k}+S_{N}-S_{k}$

因为前缀和每一个都减了 $S_k$，所以答案由 $\sum\limits_{i=1}\limits^{n} |S_i|$ 变成了 $\min\limits_{k\in[1,n]} \sum\limits_{i=1}\limits^{n} |S_i-S_k|$

$证毕$

---

那么就是找到一个 $S$ 的中位数就可以了……吗?

---

真的就这样简单吗？？？

看到 $N \le 10^7$ ，心脏骤停。如果使用排序找中位数的话是 $O(n \log n)$显然过不了！

那么我就要请出 $O(n)$ 求中位数大法了！！

可以把这个问题转化为找到第 $n/2$ 大的数，可以用类似快速排序的思想 ：

1.随机选择一个作为基准值

2.将数组分成三部分：小于基准，等于基准，大于基准。

3.如果基准值小于第 $n/2$ 大的数，递归大部分。如果基准值大于第 $n/2$ 大的数，递归小部分。如果基准值等于第 $n/2$ 大的数，直接返回。

代码如下：

long long quick_found(long long l,long long r,long long k){
	if (l==r) return sum[l];
	
	swap(sum[(l+r)>>1],sum[r]);
	int p=sum[r]; //基准值 
	
	int j=l;
	for (int i=l;i<r;i++){//确定位置 
		if (sum[i]<p){
			swap(sum[i],sum[j]);
			j++;
		}
	}
	swap(sum[j],sum[r]); //基准值放中间
	//此时基准值左边的数都比基准值小，右边的数都比它大 
	if (k==j){
		return sum[k];
	} 
	else if (k<j){
		return quick_found(l,j-1,k);
	}
	else if (k>j){
		return quick_found(j+1,r,k);
	}
	return -1;
}

这样的复杂的为什么是 $O(n)$ 呢？我太蒻了，证不了，自己去查百度

那么主函数就显而易见的了：

int main(){
	n=read();
	for (int i=1;i<=n;i++){
		a[i]=read(); suma+=a[i];
	}
	m=suma/n;//每个人应有的纸牌数
	for (int i=1;i<=n;i++){
		a[i]-=m;//让每个人都减去它，使得目标的纸牌数为0
	}
	for (int i=1;i<=n;i++){
		sum[i]=sum[i-1]+a[i];
	}
	int Tim=quick_found(1,n,n>>1);//中位数
	for (int i=1;i<=n;i++){
		ans+=abbbs(sum[i]-Tim);
	}
	printf("%lld",ans);
	return 0;
}