算是一道数学题。

设 $p[i]$ 为第 $i$ 个人分给第 $i-1$ 个人的数量（第一个人分给最后一个人）

且 $p[i]$ 可正可负，负数表示第 $i-1$ 个人给第 $i$ 个人的

则题目所求为 $Ans=|p[1]|+|p[2]|+……|p[n]|$ 的最小值

设平均数为 $ave$

则 $ave=a[i]+p[i+1]-p[i]$

设 $w[i]=p[i+1]-p[i]=ave-a[i]$

$s[i]=w[1]+w[2]+……+w[i]$ （即w的前缀和）

则 $p[i]=p[1]+s[i-1]$

所以 $Ans=|p[1]|+|p[1]+s[1]|+……|p[1]+s[n-1]|$

设 $Q=-p[1]$

则 $Ans$ 的含义就是 $0,s[1],s[2]……s[n]$ 到 $Q$ 的距离之和的最小值

所以这个 $Q$ 就是 $s$ 数组中的中位数了

#include<cstdio>
#include<cstring>
#include<cctype>
#include<cstdlib>
#include<algorithm>
#define reg register
using namespace std;
typedef long long ll;
const int N=1e5+5;
int n,a[N],tot;
ll sum[N],ans,q;
inline int read()
{
    int x=0,w=1;
    char c=getchar();
    while (!isdigit(c)&&c!='-') c=getchar();
    if (c=='-') c=getchar(),w=-1;
    while (isdigit(c))
    {
        x=(x<<1)+(x<<3)+c-'0';
        c=getchar();
    }
    return x*w;
}
int main()
{
    n=read();
    for (reg int i=1;i<=n;i++) a[i]=read(),tot+=a[i];
    tot/=n;
    for (reg int i=1;i<=n;i++) a[i]-=tot,sum[i]=sum[i-1]+a[i];
    sort(sum+1,sum+n+1);
    ll q=(n&1)?sum[(n>>1)+1]:(sum[n>>1]+sum[(n>>1)+1])>>1;
    for (reg int i=1;i<=n;i++) ans+=abs(sum[i]-q);
    printf("%lld\n",ans);
    return 0;
}