[HAOI2008]糖果传递（贪心+公式推导）

传送门

这道题其实相当于 均分纸牌 的一个进阶。

在均分纸牌中我们是这样做的：让每一堆都往左传。

让每个人的数量都减去平均数，结果可以经过简单的数学推导得

 其中S[i]是新数组的前缀和。这是均分纸牌问题的通用公式。

然后这道题，我们可以沿用这样的思想进行数学推导

 中位数证明（来自洛谷题解）：

#include<bits/stdc++.h>
#define N 1000003
#define LL long long
using namespace std;
LL a[N],c[N];
int main()
{
    int n;
    scanf("%d",&n);
    LL sum=0;
    for(int i=1;i<=n;++i)
    {
        scanf("%d",&a[i]);
        sum+=a[i];
    }
    LL ave=sum/n;
    for(int i=1;i<=n;++i)
    {
        c[i]+=a[i];
        c[i]+=c[i-1];
        c[i]-=ave;
    }
    sort(c+1,c+1+n);
    LL mid=c[(n+1)/2];//mid即x1
    LL ans=0;
    for(int i=1;i<=n;++i)
       ans+=abs(mid-c[i]);
    printf("%lld
",ans);
}