SPOJ 上有，4月份做的，贪心

var ans:qword;n,i,b1,t:longint;

a,a1:array[0..100000] of longint;

procedure qsort(l,r:longint);

var i,j,t,m:longint;

begin

i:=l;j:=r;m:=a[(l+r) div 2];

repeat

while a[i]>m do inc(i);

while a[j]<m do dec(j);

if i<=j then

begin

t:=a[i];a[i]:=a[j];a[j]:=t;

inc(i);dec(j);

end;

until i>j;

if i<r then qsort(i,r);

if l<j then qsort(l,j);

end;

begin

readln(n);

a[0]:=0;b1:=0;

for i:=1 to n do

begin

readln(a1[i]);

b1:=b1+a1[i];

end;

b1:=b1 div n;

for i:=1 to n do

begin

a[i]:=a[i-1]+a1[i]-b1;

if i=n then a[i]:=0;

end;

qsort(1,n);

if odd(n) then t:=a[n div 2+1]

else t:=a[n div 2];

ans:=0;

for i:=1 to n do ans:=ans+abs(a[i]-t);

writeln(ans);

end.

Views: 260 | Added by: dhy0077 | Rating: 0.0/0

Only registered users can add comments.
[ Sign Up | Login ]

Clever Space