Cấp phát máy tính
Xem dạng PDFChuẩn bị cho đợt làm đồ án tốt nghiệp, Trung tâm Công nghệ thông tin của Đại học Công nghiệp Hà Nội cho sinh viên mượn máy tính xách tay. Kho của Trung tâm có ~m~ máy, máy thứ ~j~ có điểm cấu hình là ~a_j~. Có ~n~ sinh viên đăng ký mượn máy; phần mềm mà sinh viên thứ ~i~ phải dùng đòi hỏi máy có điểm cấu hình tối thiểu là ~b_i~.
Máy ~j~ dùng được cho sinh viên ~i~ khi và chỉ khi ~a_j \ge b_i~. Mỗi sinh viên được nhận nhiều nhất một máy và chỉ nhận máy dùng được cho mình; mỗi máy được cấp cho nhiều nhất một sinh viên. Có thể có sinh viên không được cấp máy và có máy không được cấp cho ai.
Yêu cầu
Hãy tìm số sinh viên nhiều nhất có thể được cấp máy.
Dữ liệu vào
- Dòng thứ nhất chứa hai số nguyên dương ~n~ và ~m~ – số sinh viên và số máy;
- Dòng thứ hai chứa ~n~ số nguyên dương ~b_1, b_2, \ldots, b_n~ – yêu cầu của các sinh viên;
- Dòng thứ ba chứa ~m~ số nguyên dương ~a_1, a_2, \ldots, a_m~ – điểm cấu hình của các máy.
Kết quả ra
Ghi ra một số nguyên duy nhất là số sinh viên nhiều nhất được cấp máy.
Ràng buộc
~1 \le n, m \le 2 \cdot 10^5~; ~1 \le a_j, b_i \le 10^9~.
- Subtask 1 (10% số điểm – test 01–03): ~n, m \le 8~;
- Subtask 2 (20% số điểm – test 04–08): mọi ~b_i~ bằng nhau;
- Subtask 3 (25% số điểm – test 09–13): ~n, m \le 2000~;
- Subtask 4 (45% số điểm – test 14–20): không có ràng buộc bổ sung.
Ví dụ
Dữ liệu vào mẫu 1
5 6
6 3 9 6 12
5 2 8 6 1 10
Kết quả ra mẫu 1
4
Giải thích
Một cách cấp máy cho ~4~ sinh viên: sinh viên ~2~ (cần ~3~) nhận máy ~1~ (cấu hình ~5~); sinh viên ~1~ và sinh viên ~4~ (cùng cần ~6~) nhận máy ~4~ (cấu hình ~6~) và máy ~3~ (cấu hình ~8~); sinh viên ~3~ (cần ~9~) nhận máy ~6~ (cấu hình ~10~). Không có máy nào đủ cấu hình cho sinh viên ~5~ (cần ~12~) nên không thể cấp máy cho cả ~5~ sinh viên.
Bình luận