Tìm Trung Vị Của Hai Mảng Đã Sắp Xếp (Median of Two Sorted Arrays)
Cho hai mảng số nguyên A và B đã được sắp xếp theo thứ tự tăng dần, kích thước lần lượt là N và M.
Tiến độ của tôi ở bài này
Điểm và code bạn nộp được lưu vào tài khoản sau khi chấm bài.
Đang tải điểm của bạn…
Kiến thức và chủ đề
Kiến thức tiên quyết: Binary Search on Range, Partitioning.
Nội dung đề bài
Mô tả bài toán
Cho hai mảng số nguyên A và B đã được sắp xếp theo thứ tự tăng dần, kích thước lần lượt là N và M.
Hãy tìm giá trị trung vị (median) của mảng hợp nhất gồm N + M phần tử của hai mảng này.
- Nếu N + M lẻ: Trung vị là phần tử đứng chính giữa.
- Nếu N + M chẵn: Trung vị là trung bình cộng của 2 phần tử đứng chính giữa.
Yêu cầu thuật toán đạt độ phức tạp thời gian O(log(min(N, M))).
Quy ước nộp bài
- Chỉ cần viết một chương trình đọc stdin và in ra stdout. Bài này không yêu cầu viết hàm.
- Không dùng cout để in lời nhắc trước khi đọc dữ liệu. Lời nhắc sẽ lọt vào stdout và làm bài sai.
- Chỉ in đúng nội dung ở mục Output. Không in thêm nhãn, dòng trống hay ký tự thừa.
- Output được so khớp từng ký tự, phân biệt chữ hoa/thường và dấu câu.
Input
- Dòng đầu chứa hai số nguyên N và M (0 ≤ N, M ≤ 2 · 105, N + M ≥ 1).
- Dòng thứ hai chứa N số nguyên của mảng A (nếu N > 0).
- Dòng thứ ba chứa M số nguyên của mảng B (nếu M > 0).
Output
- In ra một số thực duy nhất là giá trị trung vị, làm tròn đến đúng 1 chữ số thập phân (fixed << setprecision(1)).
Ràng buộc
- Thời gian chạy tối đa: 1000ms.
- Giới hạn bộ nhớ: 256MB.
- Dữ liệu đầu vào tuân thủ đúng định dạng và miền giá trị được mô tả.
Ví dụ 1
Input
2 2
1 3
2 4
Output
2.5
Giải thích
Dữ liệu kiểm thử mẫu và kết quả thực thi theo yêu cầu.
Gợi ý và lời giải chỉ mở sau khi bạn bấm Nộp bài. Giáo viên và quản trị viên mở được ngay.
Góp ý & báo lỗi bài tập
Đề bài chưa rõ, test có vấn đề hay bạn có ý tưởng giúp bài tốt hơn? Gửi cho đội ngũ AI Empire nhé — mỗi góp ý đều được đọc.
