Bakser's Blog

我是逗比。

bzoj1045 中位数定理

| Comments

bzoj又挂了QAQ
环形均分纸牌模型

bzoj1045
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstring>
using namespace std;
#define N 1000100
typedef long long LL;
template<class T>
T abs(T x)
{
    return ((x>=0)?(x):(-x));
}
LL n,a[N],sum,hh,p[N],stand,ans;
int main()
{
    scanf("%lld",&n);
    for(int i(1);i<=n;i++)
    {
        scanf("%lld",a+i);
        sum+=a[i];
    }
    sum/=n;
    for(int i(1);i<n;i++)
        p[i]=p[i-1]+a[i]-sum;
    p[n]=0;
    sort(p+1,p+n+1);
    stand=p[(n+1)>>1];
    for(int i(1);i<=n;i++)
        ans+=abs(stand-p[i]);
    printf("%lld\n",ans);
    return 0;
}

Comments

comments powered by Disqus