bzoj 3293 数学整理

/**************************************************************
    Problem: 3293
    User: BLADEVIL
    Language: Pascal
    Result: Accepted
    Time:296 ms
    Memory:15852 kb
****************************************************************/
 
//By BLADEVIL
var
    n                   :longint;
    a, sum              :array[0..1000010] of int64;
    i                   :longint;
    ave                 :int64;
    ans, k              :int64;
procedure swap(var a,b:int64);
var
    c                   :int64;
begin
    c:=a; a:=b; b:=c;
end;
     
procedure qs(low,high:longint);
var
    i, j, xx            :longint;
begin
    i:=low; j:=high; xx:=sum[(i+j) div 2];
    while i<j do
    begin
        while sum[i]<xx do inc(i);
        while sum[j]>xx do dec(j);
        if i<=j then
        begin
            swap(sum[i],sum[j]);
            inc(i); dec(j);
        end;
    end;
    if i<high then qs(i,high);
    if j>low then qs(low,j);
end;
     
begin
    read(n);
    for i:=1 to n do read(a[i]);
    for i:=1 to n do sum[i]:=sum[i-1]+a[i];
    ave:=sum[n] div n;
    for i:=1 to n do sum[i]:=sum[i]-i*ave;
    qs(1,n);
    k:=sum[(1+n) div 2];
    for i:=1 to n do ans:=ans+abs(sum[i]-k);
    writeln(ans);
end.