KMIN - KMIN

Tác giả: ll931110

Ngôn ngữ: Pascal

{$MODE DELPHI}
Program KMIN;
Const
  input  = '';
  output = '';
  maxn = 50000;
Var
  a,b,d,heap: array[1..maxn] of integer;
  n,m,k,nHeap: integer;

Procedure init;
Var
  f: text;
  i: integer;
Begin
  Assign(f, input);
    Reset(f);

  Readln(f, m, n, k);
  For i:= 1 to m do read(f, a[i]);
  For i:= 1 to n do read(f, b[i]);

  Close(f);
End;

Procedure swap(var p,q: integer);
Var
  t: integer;
Begin
  t:= p;
  p:= q;
  q:= t;
End;

Procedure quicksort(x: integer);

  Procedure partition(l,h: integer);
  Var
    i,j,p: integer;
  Begin
    If l >= h then exit;

    i:= l;
    j:= h;
    p:= d[random(h - l + 1) + l];

    Repeat
      While d[i] < p do inc(i);
      While d[j] > p do dec(j);

      If i <= j then
        Begin
          If i < j then swap(d[i],d[j]);
          inc(i);
          dec(j);
        End;
    Until i > j;

    partition(l,j);
    partition(i,h);
  End;

Begin
  partition(1,x);
End;

Procedure push(v: integer);
Var
  parent,child: integer;
Begin
  inc(nHeap);
  child:= nHeap;

  parent:= child div 2;
  While (parent > 0) and (heap[parent] < v) do
    Begin
      heap[child]:= heap[parent];
      child:= parent;
      parent:= child div 2;
    End;

  heap[child]:= v;
End;

Procedure pop;
Var
  r,c,v: integer;
Begin
  v:= heap[nHeap];
  dec(nHeap);

  r:= 1;
  While r * 2 <= nHeap do
    Begin
      c:= r * 2;
      If (c < nHeap) and (heap[c + 1] > heap[c]) then inc(c);
      If v >= heap[c] then break;

      heap[r]:= heap[c];
      r:= c;
    End;

  heap[r]:= v;
End;

Procedure solve;
Var
  i,j,tmp: integer;
Begin
  d:= a;
  quicksort(m);
  a:= d;

  d:= b;
  quicksort(n);
  b:= d;

  nHeap:= 0;
  For i:= 1 to m do
    For j:= 1 to n do
      Begin
        tmp:= a[i] + b[j];
        If nHeap < k then push(tmp) else
          If tmp > heap[1] then break else
            Begin
              pop;
              push(tmp);
            End;
      End;
End;

Procedure printresult;
Var
  f: text;
  i: integer;
Begin
  d:= heap;
  quicksort(nHeap);
  heap:= d;

  Assign(f, output);
    Rewrite(f);
    For i:= 1 to nHeap do writeln(f, heap[i]);
  Close(f);
End;

Begin
  init;
  solve;
  printresult;
End.

Download