KMIN - KMIN

Tác giả: hieult

Ngôn ngữ: C++

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

Download