题意简述

环形均分纸牌。

思路分析

朴素均分纸牌

每个位置初始有纸牌 $a_i$，记 $s=\sum a_i$，则分完之后每个位置有 $\dfrac{s}{n}$，每个位置需要分出的纸牌数量记为 $A_i=a_i-\dfrac{s}{n}$。

注意 $A_i$ 可能为负数，有两种含义

• $A_i\ge 0$：表示需要将 $A_i$ 张牌从 $i$ 传到 $i+1$。

• $A_i<0$：表示需要将 $|A_i|$ 张牌从 $i+1$ 传到 $i$。

思考分纸牌的过程：

先将 $A_1$ 张牌传给 $2$ 这个位置，此时 $A_2'\to A_2+A_{i}$。

后将 $A_2'$ 张牌传给 $3$ 这个位置，此时 $A_3'\to A_3+A_2'$。

然后将 $A_k'$ 张牌传给 $k+1$ 这个位置，此时 $A_{k+1}'\to A_{k+1}+A_k'$

当前 $n-1$ 个位置的纸牌数均为 $\dfrac{s}{n}$，则第 $n$ 个位置无需再将纸牌“传给”其他位置，也可以说，$A_n'=0$。

整个过程中，传递所产生的总代价即为 $|A_1|+\sum\limits_{i=2}^n|A_i'|$。

我们发现，$A_k'$ 总会叠加在 $A_{k+1}'$ 中，不妨记 $S_i=\sum\limits_{j=1}^iA_j$。则总代价即可记为 $\sum\limits_{i=1}^n |S_i|$。

环形的均分纸牌

在这种情况下，最优方案一定也是“传递” $n-1$ 次。

我们枚举从位置 $k$ 开始不断向后“传导”的最优方案。

将 $A_k$ 张牌传给 $k+1$ 这个位置，此时 $A_{k+1}'\to A_{k+1}+A_k$

将第 $A_n'$ 张牌传给 $1$ 这个位置，此时 $A_1'=A_1+A_n'$

当前 $k\sim n,n\sim k-2$ 个位置的纸牌数均为 $\dfrac{s}{n}$，则第 $k-1$ 个位置无需再将纸牌传给其他位置，也可以说，$A_{k-1}'=0$。

我们仍然记 $S_i=\sum\limits_{j=1}^iA_j$，则从 $p$ 传导给 $p+1(k\le p<n)$ 的代价是 $S_p-S_{k-1}$。

当 $t=n$ 时，代价是 $S_n-S_{k-1}$。

当 $1\le t <k$ 时，代价是 $S_n-S_{k-1}+S_t$。

我们上文提到过 $S_n=0$，所以化简后，传递的总代价为 $\sum\limits_{i=1}^n|S_{k-1}-S_t|$。

问题在于如何找到一个 $k-1$，使得代价和最小。我们把所有 $S_i$ 画在数轴上，发现这个点取得越靠中间，它到其他点的总距离越小，代价和也就越小。所以我们取中位数就可以。

Code

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N=1e5+10;
int a[N],s[N],sum,n;
long long ans;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",a+i),sum+=a[i];
    for(int i=1;i<=n;i++)s[i]=s[i-1]+a[i]-sum/n;
    sort(s+1,s+1+n);
    for(int i=1;i<=n;i++)ans=(long long)ans+abs(s[i]-s[n/2+1]);
    printf("%lld\n",ans);
    return 0;
}

如有错误，请指出。