Phần tử nhỏ thứ K trong hai mảng đã sắp xếp

Binary-search Buổi 06 — Sắp xếp & Tìm kiếm
Points
58
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
sortsearch
Submissions
Đề 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$.

Draft saved