Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của flashmt

const maxn=50020;
type ar=array[1..maxn] of longint;
var n,m,k,nh:longint;
    h,p,a,b,c,d:ar;

procedure sort(var a:ar;l,r:longint);
var i,j,x,y:longint;
begin
     i:=l; j:=r; x:=a[(i+j) shr 1];
     repeat
           while a[i]<x do i:=i+1;
           while a[j]>x do j:=j-1;
           if i<=j then
           begin
                y:=a[i]; a[i]:=a[j]; a[j]:=y;
                i:=i+1; j:=j-1;
           end;
     until i>j;
     if i<r then sort(a,i,r);
     if l<j then sort(a,l,j);
end;

procedure rf;
var i:longint;
begin
     read(m,n,k);
     for i:=1 to m do read(a[i]);
     for i:=1 to n do read(b[i]);
     sort(a,1,m);
     sort(b,1,n);
end;

procedure update(i:longint);
var cha,con:longint;
begin
     con:=p[i];
     if con=0 then
     begin
          inc(nh); con:=nh;
          cha:=con shr 1;
          while (cha>0) and (d[h[cha]]>d[i]) do
          begin
               h[con]:=h[cha];
               p[h[con]]:=con;
               con:=cha;
               cha:=con shr 1;
          end;
          h[con]:=i; p[i]:=con;
     end
     else
     begin
          cha:=con; con:=cha shl 1;
          while con<=nh do
          begin
               if (con<nh) and (d[h[con+1]]<d[h[con]]) then inc(con);
               if d[h[con]]>=d[i] then break;
               h[cha]:=h[con];
               p[h[cha]]:=cha;
               cha:=con;
               con:=cha shl 1;
          end;
          h[cha]:=i; p[i]:=cha;
     end;
end;

function pop:longint;
var cha,con,x:longint;
begin
     pop:=h[1];
     x:=h[nh]; dec(nh);
     cha:=1; con:=2;
     while con<=nh do
     begin
          if (con<nh) and (d[h[con+1]]<d[h[con]]) then inc(con);
          if d[x]<=d[h[con]] then break;
          h[cha]:=h[con];
          p[h[cha]]:=cha;
          cha:=con; con:=cha shl 1;
     end;
     h[cha]:=x; p[x]:=cha;
end;

procedure pr;
var i,x:longint;
begin
     for i:=1 to m do
     begin
          c[i]:=1;
          d[i]:=a[i]+b[1];
          update(i);
     end;
     for i:=1 to k do
     begin
          x:=pop;
          writeln(d[x]);
          p[x]:=0;
          if c[x]<n then
          begin
               inc(c[x]);
               d[x]:=a[x]+b[c[x]];
               update(x);
          end;
     end;
end;

begin
     rf;
     pr;
end.

Code mẫu của happyboy99x

#include <algorithm>
#include <bitset>
#include <cctype>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;

typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef vector<int> vi;
typedef vector<vi> vvi;

#define sz(a) int((a).size())
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(), (c).end()
#define tr(c,i) for(typeof((c).begin()) i = (c).begin(), _e = (c).end(); it != _e; ++it)
#define present(c,x) ((c).find(x) != (c).end())
#define cpresent(c,x) (find(all(c),x) != (c).end())
#define rep(i,n) for(int i = 0, _n = (n); i < _n; ++i)
#define repd(i,n) for(int i = (n)-1; i >= 0; --i )
#define fo(i,a,b) for(int i = (a), _b = (b); i <= _b; ++i)
#define fod(i,a,b) for(int i = (a), _b = (b); i >= _b; --i)

#define INF 1000000000
#define N 50005
int a[N], b[N], p[N], m, n, k;

int main() {
    scanf( "%d%d%d", &m, &n, &k );
    rep(i,m) scanf( "%d", a + i );
    rep(i,n) scanf("%d",b+i); sort(b,b+n);
    priority_queue< ii, vii, greater<ii> > qu;
    rep(i,m) qu.push(ii(a[i]+b[0], i));
    rep(i,k) {
        ii tmp = qu.top(); qu.pop();
        printf( "%d\n", tmp.fi );
        if( p[tmp.se] < n-1 ) 
            qu.push(ii(a[tmp.se]+b[++p[tmp.se]], tmp.se));
    }
    return 0;
}

Code mẫu của ladpro98

#include <iostream>
#include <cstdio>
#include <stdlib.h>
#include <queue>
#include <algorithm>

const long maxN=50005;

long b[maxN];
long a[maxN];
long v[maxN];
long M,N,K;
using namespace std;
void sort(long l,long r);

struct e{
    long val;
    long pos;
};

struct comp{
    bool operator()(e a, e b) {
        if (a.val<b.val) return false;
        else return true;
    }
};

int main(){
    //freopen("kmin.inp","r",stdin);
    //freopen("kmin.out","w",stdout);
    scanf("%ld%ld%ld",&M,&N,&K);
    for(long i=1; i<=M; i++) scanf("%ld",&a[i]);
    for(long i=1; i<=N; i++) scanf("%ld",&b[i]);
    sort(1,N);
    for(long i=1; i<=M; i++) v[i]=1;
    priority_queue<e,vector<e>,comp> q;
    e temp;
    for(long i=1; i<=M; i++) {
        temp.val = a[i]+b[v[i]];
        temp.pos = i;
        q.push(temp);
    }
    for(long i=1; i<=K; i++) {
        temp = q.top();
        q.pop();
        printf("%ld\n",temp.val);
        if (v[temp.pos]<N) {
            v[temp.pos]++;
            temp.val = a[temp.pos]+b[v[temp.pos]];
            q.push(temp);
        }
    }
    fclose(stdin);fclose(stdout);
    return 0;
}

void sort(long l,long r) {
    if (l>=r) return;
    long p,i,j;
    p=b[rand() % (r-l+1) + l];
    i=l;j=r;
    do{
        while (b[i]<p) i++;
        while (b[j]>p) j--;
        if (i<=j) {
            if (i<j) swap(b[i],b[j]);
            i++;j--;
        }
    }while (i<=j);
    sort(l,j);
    sort(i,r);
}

Code mẫu của RR

uses math;
var
  i,n,m,k,hsize,val,ia,ib:longint;
  a,b,h,ha,hb:array[1..50111] of longint;

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

procedure swapH(a,b:longint);
    begin
      swap(h[a],h[b]);
      swap(ha[a],ha[b]);
      swap(hb[a],hb[b]);
    end;

procedure down(i:longint);
    var
      j:longint;
    begin
      j:=i shl 1;
      while (j<=hsize) do
        begin
          if (j<hsize) and (h[j+1]<h[j]) then inc(j);
          if h[j]<h[i] then swapH(i,j);
          i:=j; j:=i shl 1;
        end;
    end;

procedure up(i:longint);
    var
      j:longint;
    begin
      j:=i shr 1;
      while (i>1) and (h[i]<h[j]) do
        begin
          swapH(i,j);
          i:=j; j:=i shr 1;
        end;
    end;

procedure push(u,a,b:longint);
    begin
      inc(hsize);
      h[hsize]:=u;
      ha[hsize]:=a;
      hb[hsize]:=b;
      up(hsize);
    end;

procedure pop(var u,a,b:longint);
    begin
      u:=h[1];
      a:=ha[1];
      b:=hb[1];
      swapH(1,hsize);
      dec(hsize);
      down(1);
    end;

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

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

begin
  read(n,m,k);
  for i:=1 to n do read(a[i]);
  for i:=1 to m do read(b[i]);
  sortA(1,n);
  sortB(1,m);

  for i:=1 to n do push(a[i]+b[1],i,1);

  for i:=1 to k do
    begin
      pop(val,ia,ib);
      writeln(val);
      if ib<m then push(a[ia]+b[ib+1],ia,ib+1);
    end;
end.

Code mẫu của hieult

#include <iostream> 
#include <algorithm> 

using namespace std; 

#define MAX 50000 

int M, N, K, A[MAX+1], B[MAX+1]; 

class Element { 
      public: 
             int x, y; 
             bool operator < (Element E) { return A[x]+B[y]>A[E.x]+B[E.y]; } 
}; 

Element Heap[MAX + 1], E; 

int main() { 
    scanf("%d%d%d", &M, &N, &K); 
    for (int i = 0; i < M; scanf("%d", &A[i++])); 
    for (int i = 0; i < N; scanf("%d", &B[i++])); 
    sort(A, A+M); sort(B, B+N); 

    for (int i = 0; i < M; i++) {  
        Heap[i].x = i;  Heap[i].y = 0; 
        push_heap(&Heap[0], &Heap[i+1]);  
    } 
    int NHeap = M; 

    for (int i = 0; i < K; i++) { 
        E.x = Heap[0].x; E.y = Heap[0].y;  
        pop_heap(&Heap[0], &Heap[NHeap--]); 
        printf("%d\n", A[E.x]+B[E.y++]); 
        if (E.y < N) { 
           Heap[NHeap++] = E; 
           push_heap(&Heap[0], &Heap[NHeap]); 
        } 
    } 
    return 0; 
}

Code mẫu của ll931110

{$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.

Code mẫu của skyvn97

#include<cstring>
#include<cstdio>
#include<queue>
#include<algorithm>
#define MAX   50050
#define f   first
#define s   second
using namespace std;
typedef pair<int,int> ii;
int m,n,k;
int a[MAX];
int b[MAX];
int p[MAX];
priority_queue<ii,vector<ii>,greater<ii> > q;
void init(void) {
    scanf("%d",&m);
    scanf("%d",&n);
    scanf("%d",&k);
    int i;
    for (i=1;i<=m;i=i+1) {
        scanf("%d",&a[i]);
        p[i]=1;
    }
    for (i=1;i<=n;i=i+1) scanf("%d",&b[i]);
    while (!q.empty()) q.pop();
    sort(&a[1],&a[m+1]);
    sort(&b[1],&b[n+1]);
}
void process(void) {
    int i;
    ii x;
    for (i=1;i<=m;i=i+1) q.push(ii(a[i]+b[1],i));
    for (i=1;i<=k;i=i+1) {
        x=q.top(); q.pop();
        printf("%d\n",x.f);
        p[x.s]++;
        if (p[x.s]<=n) q.push(ii(a[x.s]+b[p[x.s]],x.s));
    }
}
int main(void) {
    init();
    process();
    return 0;
}

Code mẫu của khuc_tuan

#include <iostream>
#include <queue>
#include <cstdio>

using namespace std;

int a[50050], b[50050];
int m, n, k;

struct cmp {
    bool operator()(pair<int,int> p1, pair<int,int> p2) {
        return a[p1.first]+b[p1.second] > a[p2.first]+b[p2.second];
    }
};

priority_queue<pair<int,int>, vector<pair<int,int> >, cmp > q;

int main() {
    scanf("%d%d%d", &m, &n, &k);
    for(int i=0;i<m;++i) scanf("%d", a+i);
    for(int i=0;i<n;++i) scanf("%d", b+i);
    sort( a, a+m);
    sort( b, b+n);
    for(int i=0;i<m;++i) q.push( make_pair( i, 0) );
    for(int kk=0;kk<k;++kk) {
        pair<int,int> p = q.top();
        q.pop();
        printf("%d\n", a[p.first] + b[p.second]);
        if(p.second+1<n) q.push( make_pair( p.first, p.second+1) ); 
    }
    return 0;
}