KMIN - KMIN
Tác giả: ladpro98
Ngôn ngữ: C++
#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);
}