DCT04 – Sắp xếp hai nửa
Xem dạng PDF
Mã bài:
dct04
Điểm:
1,5 (OI)
Giới hạn thời gian:
2.0s
Giới hạn bộ nhớ:
512M
Dữ liệu vào:
stdin
Dữ liệu ra:
stdout
Tác giả:
Dạng bài
Đề bài
Cho một dãy n số nguyên chưa chắc có thứ tự. Hãy in dãy sau khi sắp xếp không giảm.
Chuyên đề hướng dẫn thuật toán Merge Sort: chia hai nửa, sắp xếp riêng từng nửa rồi trộn hai dãy đã sắp xếp.
Dữ liệu vào
Dòng 1: Số nguyên n. Dòng 2: n số nguyên a1, a2, ..., an.
Dữ liệu ra
In n số nguyên sau khi sắp xếp không giảm, cách nhau một dấu cách.
Ràng buộc
1 ≤ n ≤ 200000; -10^9 ≤ ai ≤ 10^9.
Ví dụ
Ví dụ 1
Input
6
7 2 6 1 2 -3
Output
-3 1 2 2 6 7
Giải thích: Dãy tăng dần được phép có các phần tử bằng nhau.
Bình luận