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.