khangvinhc3

Cho 2 dãy số nguyên A và B. 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

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

Example

Input:
4 4 6
1
2
3
4
2
3
4
5

Output:
3
4
4
5
5
5

Giới hạn

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

nộp bài chỗ này ạ http://vn.spoj.com/submit/KMIN/

 

 | 
RR

Lần sau bạn vào đề bài trên VNOI, rồi click vào phần thảo luận nhé. Mình vừa chuyển bài của bạn vào phần thảo luận của bài đó.

Bạn post đúng chỗ thì cũng ko cần viết lại đề.

khoaplt

Ý tưởng thuật toán.

Ta sẽ phân tích lại yêu cầu đề bài. Như trên đề bài là tìm K số đầu tiên của \(C\), ta có thể hiểu là tìm K cặp \((i, j)\) khác nhau sao cho tổng \(A_i+B_j\) của các cặp đấy là nhỏ nhất có thể. Như thế này ta có nhận xét: với mỗi phần tử \(A_i\), nếu \(B_e < B_k\) thì nếu \(A_i + B_e\) không nằm trong K số đầu tiên thì \(A_i + B_k\) sẽ không nằm trong K số đầu tiên. Từ đấy ta có thuật toán, với mỗi \(A_i\) tìm thằng \(B_j\) nhỏ nhất sao cho tổng \(A_i+B_j\) chưa được xét đến. Gọi chỉ số \(j\) tìm được là \(min(i)\). Sau đấy thì ta sẽ có số tiếp theo trong dãy K số đầu tiên sẽ là tổng \(A_i+B_{min(i)}\) nhỏ nhất với i chạy từ \(1 -> N\). Gọi cặp tìm được là \(A_{X}+B_{min(X)}\). Sau khi cho tổng này vào trong dãy đáp án, thi ta phải cập nhật lại \(min(X)\). Quy trình sẽ lặp đi lặp lại cho tới khi nào dãy đáp án có đủ K số.

Tối ưu thuật toán

Để thuật toán chạy hiệu quả ta cần phải để ý 2 việc sau:

  • Thực hiện việc tìm X một cách hiệu quả: ta sẽ cần phải dùng tới một cấu trúc có thể lấy giá trị nhỏ nhất của một tập một cách nhanh chóng. Một trong những cấu trúc cơ bản để giải quyết bài toán là cấu trúc heap cho phép ta lấy giá trị nhỏ nhất của một tập trong độ phức tạp \(O(log_2 N)\) và các thao tác thêm vào cũng như bớt ra một phần tử cũng chỉ mất \(O(log_2 N)\).
  • Thực hiện việc cập nhật min(X) một cách hiệu quả: ban đầu ta sẽ phải sort lại mảng \(B\). Với thuật toán quicksort, việc sắp xếp này chỉ tốn \(O(N log_2 N)\) thời gian.

Dựa trên thuật toán trên, nếu cài đặt hiệu quả thì thời gian chạy sẽ không vượt quá \(O(max(N, K) * log_2 N)\)

© VNOI Team 2015