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);
}

Download