题目链接： 122.糖果传递

题目描述：

有n个小朋友坐成一圈，每人有a[i]个糖果。

每人只能给左右两人传递糖果。

每人每次传递一个糖果代价为1。

求使所有人获得均等糖果的最小代价。
输入格式

第一行输入一个正整数n，表示小朋友的个数。

接下来n行，每行一个整数a[i]，表示第i个小朋友初始得到的糖果的颗数。
输出格式

输出一个整数，表示最小代价。

数据范围 ： 1≤n≤1000000

解题思想：

类似于经典题目：均分纸牌，可以说是前面的七夕祭的简单化。
先预处理，计算每个人的钱减去均值后的前缀和，记为s[i]
因为是一个环形，所以，我们可以先简化，思考一下线性结构。

仔细想一想，不难发现，线性均分纸牌中的最后一个人，只需要拿着前面人给的牌，或者让前面的人从他这里拿走牌，实际上他自己什么也没有干。

与此类似，环形均分纸牌中也存在着这么一个“懒人”，而我们要做的，就是从这个“懒人”后将环斩断，并展开形成一个线性结构。

在线性结构中，有：

a[1] s[1]
a[2] s[2]
…
a[n] s[n]

其中a[i]是原始数据（每个人的牌数），s[i]是前i个人的前缀和

在环形结构中，如果将环从第k个人之后斩断（将k作为队列末尾），则有：

a[k+1] s[k+1]-s[k]
a[k+2] s[k+2]-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[i]| (1<=i<=n)

到了环形结构，也与此类似，代价为：

Σ|s[i]-s[k]| (1<=i<=n)

（以上两个式子中的 s[i] 都是减过平均值后的前缀和）

由此表达式，其实不难发现，与前面的 106 货仓选址 十分类似，只需要找到前缀和数组中的中位数，然后计算即可。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
#define ll long long
#define xx int
#define N (int)1e6+10
#define Foor(i,j,n) for(int i=j;i<=n;i++)
#define Ford(i,j,n) for(int i=j;i>=n;i--)
inline xx read()
{
    xx f=1,x=0; char ch=getchar();
    while(ch>'9'||ch<'0') { if(ch=='-') f=-1;  ch=getchar();    }
    while(ch>='0'&&ch<='9') { x=x*10+ch-'0'; ch=getchar();  }
    return f*x;
}
xx n,x;
ll s[N],evr,place;
unsigned long long ans;
int main()
{
    n=read();
    s[0]=0;
    Foor(i,1,n)
    {
        x=read();   s[i]=s[i-1]+x;
    }
    evr=s[n]/n;     //average 

    Foor(i,1,n)
        s[i]-=i*evr;    //处理成，每个人的钱减去均值后的前缀和
    sort(s+1,s+n+1);

    if(n&1) place=s[n>>1];
    else place=s[n/2];      //找中位数

    ans=0;
    Foor(i,1,n)
        ans+=abs(s[i]-place);


    printf("%lld\n",ans);
    return 0;
}

/*
草稿：
n=4
1
2
5
4
s[i]:
1
3
8
12

evr=3
s[i]-i*evr:
-2
-3
-1
0

s[k]==-1
*/