Mô tả
Dịp siêu sale cuối năm, Tổng Kho Bắc và Tổng Kho Nam cùng dồn hàng về trung tâm phân phối chính. Mỗi kho đã xuất sẵn một danh sách mã đơn hàng theo thứ tự tăng dần (mã nhỏ hơn nằm trước). Trưởng kho muốn gom hai danh sách này thành một bảng tổng hợp duy nhất, vẫn giữ đúng thứ tự tăng dần để đối soát nhanh với hệ thống vận chuyển.
Nhiệm vụ của bạn là viết chương trình nhận hai mảng số nguyên đã sắp xếp tăng dần, rồi trộn chúng thành một mảng mới cũng sắp xếp tăng dần. Quan trọng: bạn phải tận dụng tính chất đã sẵn thứ tự của hai mảng đầu vào, chứ không được đổ tất cả vào một mảng rồi sắp xếp lại từ đầu — làm vậy sẽ chậm hơn mức cần thiết.
Đầu vào
- Dòng đầu chứa số nguyên
m— số lượng đơn hàng của Tổng Kho Bắc (1 ≤ m ≤ 10^5). - Dòng thứ hai chứa
msố nguyên cách nhau bởi dấu cách — mã đơn hàng của Tổng Kho Bắc, đã sắp xếp tăng dần. - Dòng thứ ba chứa số nguyên
n— số lượng đơn hàng của Tổng Kho Nam (1 ≤ n ≤ 10^5). - Dòng thứ tư chứa
nsố nguyên cách nhau bởi dấu cách — mã đơn hàng của Tổng Kho Nam, đã sắp xếp tăng dần.
Đầu ra
- Một dòng duy nhất chứa
m + nsố nguyên cách nhau bởi dấu cách — danh sách mã đơn hàng sau khi trộn, sắp xếp tăng dần.
Ràng buộc
- 1 ≤ m, n ≤ 10^5.
- Mỗi mã đơn hàng là số nguyên có giá trị tuyệt đối không vượt quá 10^9.
- Tổng số phần tử m + n không vượt quá 2 × 10^5.
- Hai mảng đầu vào đã được sắp xếp tăng dần (không giảm), có thể chứa mã trùng nhau giữa hai kho.
Ví dụ
Ví dụ 1:
Đầu vào:
3 1001 1003 1007 4 1002 1004 1005 1009
Đầu ra:
1001 1002 1003 1004 1005 1007 1009
Giải thích từng bước: Đặt con trỏ i ở đầu mảng Bắc (1001), con trỏ j ở đầu mảng Nam (1002). So sánh từng cặp: 1001 < 1002 nên lấy 1001, tiến i. Tiếp theo 1003 > 1002 nên lấy 1002, tiến j. Cứ thế luân phiên chọn mã nhỏ hơn: 1003, 1004, 1005, 1007, và cuối cùng 1009. Khi một bên hết, đổ toàn bộ phần còn lại của bên kia vào kết quả.