Dãy K min. Vào làm nào

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

Theo mình với dữ liệu là <=50 000 thì ta có thể làm theo cách "thô nhất" là xếp tất cả rồi đếm thì cũng ko sao. Mình nghĩ vậy. Tuy vậy, với bài này, mình nghĩ là chỉ cần xếp A và B thôi, sau khi xếp, ta sẽ xét các phần tử ai và bj rồi từ kết quả so sánh này để tăng biến đếm, cho đến khi biến đêm=k thì in kết quả và out. Các bạn nghĩ sao.

Bài này nếu n=m=50000 thì dãy c có 2.500.000.000 phần tử. Như vậy với giải thuật tự nhiên là hoàn toàn không thể được.
Đúng như bạn nói ta chỉ cần quicksort(a) và quicksort(b) theo chiều không giảm
+ Chọn số đầu tiên hiển nhiên là a[1]+b[1] rồi.
+ Thế số tiếp theo sẽ là số nào. Trước mắt có 2 số có khả năng nhất đó là a[1]+b[2] hoặc a[2]+b[1] và như vậy số nào nhỏ hơn thì ta chọn thôi.
Tổng quát quá:
Ở bước thứ x ta chọn a[i]+b[j] -> ở bước thứ x+1 ta chọn max(a[i+1]+b[j], a[i]+b[j+1]). Và hiển nhiên khi nhìn vào kết quả bạn sẽ biết tăng i hay tăng j rồi.

Uhm, ý mình là thế đó. ^^

Chán ghê, đội tin trường mình ko thấy lên. Do gần thi học kì và thi chuyển cấp rồi. Mà có lên cũng ko vui cho lắm, do khả năng còn thấp quá

Ad đọc thử bài chó sói và cừu non đi, thấy bài đó vui vui nên post lên. Dĩ nhiên bài đó mình còn làm được nên đối với ad là quá dễ. Tuy nhiên ad có thể cải tiến cho khó hơn. Tăng độ lớn dữ liệu chẳng hạn.