Cấp phát máy tính

Xem dạng PDF

Gửi bài giải

Điểm: 1,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout

Dạng bài

Chuẩ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

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.