BZOJ 2620 1045 3293 四倍经验 环形均分纸牌问题

不放题面了，三道都差不多是裸题，CQOI和HAOI是真正的双倍经验，好像可以直接交。

有一些数学的成分，考虑分到中位数是一定最优的。至于证明请找suika，我不会

// luogu-judger-enable-o2
#include <cstdio>
#include <algorithm>
#include <cctype>
using namespace std;
const int N = 1100000;
long long a[N],n;
long long s[N];
inline char nc() {
    static char buf[100000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline long long read() {
    long long x=0,f=1;char ch=nc();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=nc();}
    while(isdigit(ch)){x=((x+(x<<2))<<1)+(ch^'0');ch=nc();}
    return x*f;
}
int abs(int x){return x>0?x:-x;}
int main() {
    n=read();
    long long sum=0;
    for(int i=1;i<=n;i++)a[i]=read(),sum+=a[i];
    sum/=n;
    for(int i=1;i<=n;i++)
        s[i]=s[i-1]+a[i]-sum;
    sort(s+1,s+n+1);
    int m = s[n+1>>1];
    long long ans=0;
    for(int i=1;i<=n;i++)
        ans+=abs(s[i]-m);
    printf("%lld
",ans);
}