Diễn đàn tin học Nguyễn Văn Linh

The second house for every one
 
IndexTrợ giúpTìm kiếmThành viênĐăng kýĐăng Nhập

Share | 
 

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

Xem chủ đề cũ hơn Xem chủ đề mới hơn Go down 
Tác giảThông điệp
littlelee
Admin
Admin


Tổng số bài gửi : 415
Join date : 20/12/2009
Age : 21
Đến từ : Nghĩa địa

Bài gửiTiêu đề: Dãy K min. Vào làm nào   Fri 19 Mar 2010, 18:05

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
Về Đầu Trang Go down
littlelee
Admin
Admin


Tổng số bài gửi : 415
Join date : 20/12/2009
Age : 21
Đến từ : Nghĩa địa

Bài gửiTiêu đề: Re: Dãy K min. Vào làm nào   Sun 21 Mar 2010, 20:21

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.
Về Đầu Trang Go down
administrators
Gà nhỏ


Tổng số bài gửi : 29
Join date : 15/03/2010

Bài gửiTiêu đề: Re: Dãy K min. Vào làm nào   Sun 21 Mar 2010, 20:47

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.
Về Đầu Trang Go down
littlelee
Admin
Admin


Tổng số bài gửi : 415
Join date : 20/12/2009
Age : 21
Đến từ : Nghĩa địa

Bài gửiTiêu đề: Re: Dãy K min. Vào làm nào   Sun 21 Mar 2010, 21:24

Uhm, ý mình là thế đó. ^^
Về Đầu Trang Go down
littlelee
Admin
Admin


Tổng số bài gửi : 415
Join date : 20/12/2009
Age : 21
Đến từ : Nghĩa địa

Bài gửiTiêu đề: Re: Dãy K min. Vào làm nào   Sun 21 Mar 2010, 21:26

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á frown

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.
Về Đầu Trang Go down
Sponsored content




Bài gửiTiêu đề: Re: Dãy K min. Vào làm nào   Today at 18:53

Về Đầu Trang Go down
 
Dãy K min. Vào làm nào
Xem chủ đề cũ hơn Xem chủ đề mới hơn Về Đầu Trang 
Trang 1 trong tổng số 1 trang

Permissions in this forum:Bạn không có quyền trả lời bài viết
Diễn đàn tin học Nguyễn Văn Linh :: Góc tin học :: Lớp chuyên tin-
Chuyển đến