NKSGAME - VOI08 Trò chơi với dãy số

Tác giả: RR

Ngôn ngữ: Pascal

uses math;
const
  MAXN=100111;

var
  n:longint;
  a:array[0..1,1..MAXN] of longint;
  res,i,j:longint;

procedure swap(var a,b:longint);
    var
      tmp:longint;
    begin
      tmp:=a; a:=b; b:=tmp;
    end;

procedure sort(k,l,r:longint);
    var
      i,j,mid:longint;
    begin
      i:=l; j:=r; mid:=a[k,l+random(r-l+1)];
      repeat
        while a[k,i]<mid do inc(i);
        while a[k,j]>mid do dec(j);
        if i<=j then
          begin
            swap(a[k,i],a[k,j]);
            inc(i); dec(j);
          end;
      until i>j;
      if i<r then sort(k,i,r);
      if l<j then sort(k,l,j);
    end;

begin
  read(n);
  for i:=1 to n do read(a[0,i]);
  for i:=1 to n do read(a[1,i]);

  sort(0,1,n);
  sort(1,1,n);

  i:=1; j:=n; res:=abs(a[0,i]+a[1,j]);
  while (i<n) or (j>1) do
    begin
      if (i=n) then dec(j)
      else if (j=1) then inc(i)
      else if abs(a[0,i+1]+a[1,j]) < abs(a[0,i]+a[1,j-1]) then inc(i)
      else dec(j);

      res:=min(res,abs(a[0,i]+a[1,j]));
    end;
  writeln(res);
end.

Download