BZOJ-3293/1045/1465 分金币

Description

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

假设第x个人给左面的量为，顺时针方向为正，平均值为C，那么则有以下方程：



.....

转化一下：


......

这玩意不是差分吗？？？那么只需要找一个使得答案最小
答案==
那么只要把cf数组搞出来求一个中位数就好了。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
ll n,w[1001000];
ll sum,c[1001000],ans;
ll read()
{
    char ch=getchar(); ll re=0;
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9')
        re=(re<<1)+(re<<3)+ch-'0',ch=getchar();
    return re;
}
ll Abs(ll x){return x>0?x:-x;}
int main()
{
    n=read();
    for(int i=1;i<=n;i++) {w[i]=read(); sum+=w[i];}
    sum/=n; ll now=0;
    for(int i=n-1;i;i--)
    {
        now+=sum-w[i];
        c[i]=now;
    }
    c[n]=0;
    sort(c+1,c+n+1);
    ll wn=c[n%2==0?n/2:n/2+1];
    for(int i=1;i<=n;i++)
        ans+=Abs(wn-c[i]);
    printf("%lld\n",ans);
    return 0;
}