记录编号	92107	评测结果	AAAAAAAAAA
题目名称	[UVa 11300]分金币	最终得分	100
用户昵称	rpCardinal	是否通过	通过
代码语言	C++	运行时间	0.068 s
提交时间	2014-03-18 15:44:53	内存使用	7.92 MiB

#include <cstdio>

inline long long abs(long long x)
{return x>=0?x:(-x);}

char ch;
inline void read(long long &x)
{
    x=0; ch=getchar();
    while (ch<=32) ch=getchar();
    while (ch>32)
    {
        x=x*10+ch-48;
        ch=getchar();
    }
}

int n,i;
long long sum,a[1000010],x,ans;

long long qselect(int l,int r,int k)
{
    int i=l,j=r;
    long long x=a[l];
    while (i<j)
    {
        while (i<j&&a[j]>=x) j--;
        a[i]=a[j];
        while (i<j&&a[i]<=x) i++;
        a[j]=a[i];
    }
    a[i]=x;
    if (i-l>k) return qselect(l,i-1,k);
    if (i-l<k) return qselect(i+1,r,k-i+l-1);
    return a[i];
}

int main()
{
    freopen("Wealth.in","r",stdin);
    freopen("Wealth.out","w",stdout);
    while (scanf("%d",&n)==1)
    {
        ans=sum=0;
        for (i=1;i<=n;++i) {read(a[i]); sum+=a[i];}
        sum/=n; for (i=1;i<=n;++i) a[i]-=sum;
        a[0]=0; for (i=1;i<n;++i) a[i]+=a[i-1];
        x=qselect(0,n-1,n/2);
        for (i=0;i<n;++i) ans+=abs(x-a[i]);
        printf("%lld\n",ans);
    }
    fclose(stdin); fclose(stdout);
    return 0;
}