1045: [HAOI2008] 糖果传递

题目连接：

http://www.lydsy.com/JudgeOnline/problem.php?id=1045

Description

有n个小朋友坐成一圈，每人有ai个糖果。每人只能给左右两人传递糖果。每人每次传递一个糖果代价为1。

Input

小朋友个数n 下面n行 ai

Output

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

Sample Input

4

1

2

5

4

Sample Output

4

Hint

100% n<=987654321

题意

题解：

环状均分纸牌

显然最后每个人都剩下sum/n张纸牌，p[i]表示这个人给下一个人多少张纸牌

显然p[i]=a[i]+p[i-1]-sum/n

p[i]-p[i-1]=a[i]-sum/n,所以p[i]-p[i-1]+p[i-1]-p[i-2]+.....-p[1] = sigma(i)(a[i]-sum/n)

即p[i]=sigma(i)(a[i]-sum/n)+p[1]

显然sigma(i)(a[i]-sum/n)是定值，所以p[1]是所有sigma(i)(a[i]-sum/n)的中位数就好了

注意，该题的数据范围有毒，要开long long,maxn至少1e6

代码

#include<bits/stdc++.h>

using namespace std;

const int maxn = 1e7+2;

long long a[maxn],c[maxn];

long long sum = 0;

int main()

{

    int n;

    scanf("%d",&n);

    for(int i=1;i<=n;i++)

    {

        scanf("%lld",&a[i]);

        sum+=a[i];

    }

    long long ave = sum/n;

    for(int i=1;i<=n;i++)

        c[i]=c[i-1]+a[i]-ave;

    sort(c+1,c+1+n);

    long long ans = 0;

    for(int i=1;i<=n;i++)

        ans+=abs(c[n/2+1]-c[i]);

    cout<<ans<<endl;

}