BZOJ3293: [Cqoi2011]分金币

2024-04-03 08:19:24

Description

圆桌上坐着n个人，每人有一定数量的金币，金币总数能被n整除。每个人可以给他左右相邻的人一些金币，最终使得每个人的金币数目相等。你的任务是求出被转手的金币数量的最小值。

Input

第一行为整数n（n>=3），以下n行每行一个正整数，按逆时针顺序给出每个人拥有的金币数。

Output

输出被转手金币数量的最小值。

Sample Input

4
1
2
5
4

Sample Output

4
样例解释
设四个人编号为1,2,3,4。第3个人给第2个人2个金币（变成1,4,3,4），第2个人和第4个人分别给第1个人1个金币。

HINT

N<=<=100000,总金币数<=10^9

设X[i]为第i个人给他下一个人的金币数，T表示最终每人应该得到的金币数。

则X[i-1]+A[i]-X[i]=T，移项得X[i]=X[i-1]+A[i]-T。

但是我们是不能直接解方程的，因为虽然方程有N个，但有一个是没用的。

我们忽略第一个方程，即让X[0]=0，然后我们可以发现这可以理解为坐标轴上N个点，我们要找一个点到其他点距离之和最短。

排序中位数即可。

#include<cstdio>

#include<cctype>

#include<queue>

#include<cmath>

#include<cstring>

#include<algorithm>

#define rep(i,s,t) for(int i=s;i<=t;i++)

#define dwn(i,s,t) for(int i=s;i>=t;i--)

#define ren for(int i=first[x];i;i=next[i])

using namespace std;

const int BufferSize=<<;

char buffer[BufferSize],*head,*tail;

inline char Getchar() {

    if(head==tail) {

        int l=fread(buffer,,BufferSize,stdin);

        tail=(head=buffer)+l;

    }

    return *head++;

}

inline int read() {

    int x=,f=;char c=Getchar();

    for(;!isdigit(c);c=Getchar()) if(c=='-') f=-;

    for(;isdigit(c);c=Getchar()) x=x*+c-'';

    return x*f;

}

typedef long long ll;

const int maxn=;

int n,A[maxn];

ll ans,sum,C[maxn];

int main() {

    n=read();rep(i,,n-) sum+=(A[i]=read());

    sum/=n;rep(i,,n-) C[i]=C[i-]+A[i]-sum;

    sort(C,C+n);

    rep(i,,n-) ans+=abs(C[i]-C[n>>]);

    printf("%lld\n",ans);

    return ;

}

码农公寓