Trộn hai dãy đã sắp xếp
Points
19
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
sortsearch
Đề bài
Cho hai dãy số nguyên $A$ (gồm $N$ phần tử) và $B$ (gồm $M$ phần tử) đều đã được sắp xếp theo thứ tự không giảm. Hãy dùng kỹ thuật hai con trỏ để trộn hai dãy thành một dãy duy nhất có $N + M$ phần tử cũng được sắp xếp không giảm trong thời gian $O(N + M)$.
Dữ liệu vào
Dòng đầu chứa hai số nguyên $N$ và $M$. Dòng thứ hai chứa $N$ số nguyên của dãy $A$. Dòng thứ ba chứa $M$ số nguyên của dãy $B$.
Dữ liệu ra
Một dòng chứa $N + M$ số nguyên sau khi trộn.
Ví dụ
| Input | Output |
|---|---|
| 3 4\n1 4 7\n2 3 7 9 | 1 2 3 4 7 7 9 |
| 2 2\n10 20\n1 2 | 1 2 10 20 |
Giới hạn
$1 \le N, M \le 10^5$, $|A_i|, |B_j| \le 10^9$.
Community Discussion