讨论 / pascal的。。60分。。后面会超时啊。。
kytdfy 2010-11-09 13:00:00
点我顶贴 收藏 删除
program hy;

var

i,n,m,x1,y1,x2,y2,k:longint;

mi:double;

a:array[1..100000] of longint;

procedure kp(l,r:longint);

var

t,x,y,mm:longint;

begin

x:=l;

y:=r;

mm:=a[l];

repeat

while a[x]<mm do inc(x);

while a[y]>mm do dec(y);

if x<=y then

begin

t:=a[x];

a[x]:=a[y];

a[y]:=t;

inc(x);

dec(y);

end;

until y<x;

if l<y then kp(l,y);

if x<r then kp(x,r);

end;

procedure zhao(l,r:longint);

var

t:longint;

begin

t:=(l+r) div 2;

if a[t]=mi then

begin

k:=a[t];

exit;

end;

if (l+1=r) or (l=r) then

if abs(a[l]-mi)<abs(a[r]-mi) then

begin

k:=a[l];

exit;

end

else

begin

k:=a[r];

exit;

end;

if a[t]<mi then zhao(t,r);

if a[t]>mi then zhao(l,t);

end;

begin

readln(n);

for i:=1 to n do

read(a[i]);

kp(1,n);

readln(m);

for i:=1 to m do

begin

readln(x1,y1,x2,y2);

if (y1>0) and (y2>0) then writeln(abs(x1-x2)+abs(y1-y2))

else if (y1<0) and (y2<0) then writeln(abs(x1-x2)+abs(y1-y2))

else

begin

mi:=(x1+x2)/2;

if mi<=a[1] then k:=a[1]

else if a[n]<=mi then k:=a[n]

else zhao(1,n);

writeln(abs(x1-k)+abs(x2-k)+abs(y1-y2));

end;

end;

end.

查看更多回复
提交回复