BZOJ3293: [Cqoi2011]分金币（数学）

3293: [Cqoi2011]分金币

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 1596  Solved: 969
[Submit][Status][Discuss]

Description

圆桌上坐着n个人，每人有一定数量的金币，金币总数能被n整除。每个人可以给他左右相邻的人一些金币，最终使

得每个人的金币数目相等。你的任务是求出被转手的金币数量的最小值。

Input

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

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

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

Source

思路：高中数学就讲过了，构造关于第一位的方程，可以得到每个数应该移动多少个，由于是代价，我们要加绝对值，然后是一个绝对值公式，取中位数时有最小值。 这里用nth_element来得到中位数。

#include<bits/stdc++.h>
#define ll long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int maxn=1000010;
int a[maxn],d[maxn]; ll av,ans;
void read(int &x){
    x=0; char c=getchar();
    while(c>'9'||c<'0') c=getchar();
    while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
}
int main()
{
    int N; scanf("%d",&N);
    rep(i,1,N) read(a[i]),av+=a[i]; av/=N;
    rep(i,2,N) d[i]=d[i-1]+av-a[i];
    nth_element(d+1,d+(N+1)/2,d+N+1);
    int num=d[(N+1)/2];
    rep(i,1,N) ans+=abs(d[i]-num);
    printf("%lld
",ans);
    return 0;
}