KMIN

2017-08-04

Content:

1. Bài gốc

SPOJ KMIN

2. Đề bài

Cho 2 dãy số nguyên A và B có M và N phần tử. Với mọi số A[i] thuộc A và B[j] thuộc B người ta tính tổng nó. Tất cả các tổng này sau khi được sắp xếp không giảm sẽ tạo thành dãy C.

Nhiệm vụ của bạn là: Cho 2 dãy A, B. Tìm K số đầu tiên trong dãy C.

Giới hạn:

  • 1 ≤ M, N, K ≤ 50000
  • 1 ≤ Ai, Bi ≤ 109

Định dạng test

Input:

  • Dòng đầu tiên gồm 3 số: M, N, K.
  • M dòng tiếp theo gồm M số mô tả dãy A.
  • N dòng tiếp theo gồm N số mô tả dãy B.

Output:

  • Gồm K dòng tương ứng là K phần tử đầu tiên trong dãy C.

Ví dụ:

input:
4 4 6
1
2
3
4
2
3
4
5
---
output:
3
4
4
5
5
5

3. Thuật toán

Giả sử đã chọn được a[i] + b[j] là phần tử để đưa vào K số, để tìm phần tử “tiềm năng” tiếp theo, có hai trường hợp:

  • a[k] + b[j], với a[k] là phẩn tử nhỏ nhất và lớn hơn hoặc bằng a[i] trong dãy A.
  • a[i] + b[k], với b[k] là phần tử nhỏ nhất và lớn hơn hoặc bằng b[j] trong dãy B.

Giả sử chọn cách tiếp cận thứ nhất, để tối ưu thuật toán ta sử dụng 2 kĩ thuật sau:

  • Sắp xếp mảng a không giảm: giả sử đã chọn a[i] + b[j], thì ứng viên “tiềm năng” tiếp theo sẽ là a[i+1] + b[j].
  • Sử dụng cấu trúc heap để chọn ra phần tử nhỏ nhất trong những a[i] + b[j] “tiềm năng” (và cả vị trí i, j của nó).

4. Source code

Ngôn ngữ: C++.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

typedef pair<ll, ii> lii;
const int N = 5e4 + 5;
int m, n, k;
ll a[N], b[N];
vector<ll> res;
priority_queue<lii, vector<lii>, greater<lii> > Q;

int main() {

    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    // input
    cin >> m >> n >> k;
    FOR(i,1,m) cin >> a[i];
    FOR(i,1,n) cin >> b[i];

    // preprocessing
    sort(a+1, a+m+1);
    FOR(i,1,n) Q.push(mp(a[1] + b[i], mp(1, i)));

    // solve
    while(k--) {
        lii p = Q.top();
        res.pb(p.fi);

        int i = p.se.fi;
        int j = p.se.se;

        // update
        Q.pop();
        if (i+1 <= m)
          Q.push(mp(a[i+1] + b[j], mp(i+1, j)));
    }

    // output
    REP(i,sz(res)) {
        cout << res[i];
        if (i+1 < sz(res)) cout << '\n';
    }

    return 0;
}

5. Độ phức tạp

O(max(M, n) * logN)