[HAOI2008]糖果传递

环形均分纸牌
对于非环形均分纸牌，记$s\left [ i \right ]$为前i项的和，ave 为平均数
可得交换数量为

$$\sum_{i=1}^{n}\left | \left ( i*ave-s\left [ i \right ] \right ) \right |$$

记$S\left [ i \right ]$为前i项，每项减去ave 的和
则交换数量为

$$\sum_{i=1}^{n}\left | \left ( S\left [ i \right ] \right ) \right |$$

对于环形均分纸牌，设在第k 个人处断开
则$S\left [ \right ]$为

$$S\left [ k +1\right ]-S\left [ k \right ],S\left [ k +2\right ]-S\left [ k+1 \right ]...$$ $$S\left [ n\right ]-S\left [ k \right ],S\left [ 1 \right ]+S\left [ n\right ]-S\left [ k \right ]...$$ $$S\left [ k \right ]+S\left [ n\right ]-S\left [ k \right ]$$

根据定义可得$S\left [ n \right ]=0$
总交换数量为

$$\sum_{i=1}^{n}\left | S\left [ i \right ] -S\left [ k \right ]\right |$$

取中位数即可

#include<cstdio>
#include<algorithm>
#define LL long long
using namespace std;
const int N=1000050;
int n,w[N];
LL sum=0,s[N],ans=0;
inline int read()
{
    register int x=0,t=1;
    register char ch=getchar();
    while (ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
    if (ch=='-') t=-1,ch=getchar();
    while (ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
    return x*t;
}
int main()
{
    n=read();
    for(int i=1;i<=n;i++) w[i]=read(),sum+=w[i];
    int ave=sum/n;
    for(int i=1;i<=n;i++) w[i]-=ave;
    for(int i=1;i<=n;i++) s[i]=s[i-1]+w[i];
    sort(s+1,s+n+1);
    for(int i=1;i<=n;i++) ans+=abs(s[i]-s[(n+1)/2]);
    printf("%lld",ans);
    return 0;
}