Phần tử nhỏ thứ K trong hai mảng đã sắp xếp
Points
58
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
sortsearch
Đề bài
Cho hai dãy số nguyên $A$ (kích thước $N$) và $B$ (kích thước $M$) đều đã được sắp xếp theo thứ tự không giảm, và một số nguyên dương $K$ ($1 \le K \le N + M$). Hãy dùng tìm kiếm nhị phân để tìm phần tử nhỏ thứ $K$ trong hợp của hai dãy trong thời gian $O(\log(\min(N, M)))$.
Dữ liệu vào
Dòng đầu chứa ba số nguyên $N, M, K$. 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 số nguyên duy nhất là phần tử nhỏ thứ $K$.
Ví dụ
| Input | Output |
|---|---|
| 4 3 5\n2 3 6 7\n1 4 8 | 6 |
| 2 2 1\n10 20\n5 15 | 5 |
Giới hạn
$1 \le N, M \le 10^5$, $1 \le K \le N + M$, $|A_i|, |B_j| \le 10^9$.
Community Discussion