Khiêu vũ

Xem dạng PDF

Mô tả bài toán

Trong một lớp học có ~ n ~ bạn nam và ~ m ~ bạn nữ. Các bạn nam có chiều cao lần lượt là ~ a_1, a_2, ..., a_n ~, và các bạn nữ có chiều cao lần lượt là ~ b_1, b_2, ..., b_m ~. Nhân dịp lễ tổng kết cuối năm, cả lớp tổ chức buổi khiêu vũ với điều kiện:

  • Một đôi khiêu vũ hợp lệ khi bạn nam phải cao hơn bạn nữ.
  • Mỗi bạn chỉ được tham gia tối đa một đôi khiêu vũ.

Yêu cầu: Hãy tính số lượng cặp đôi khiêu vũ nhiều nhất thỏa mãn các điều kiện trên.


Input
  • Dòng đầu tiên chứa hai số nguyên ~ n, m ~ (1 ≤ ~ n, m ~ ≤ ~ 10^5 ~) – số lượng bạn nam và bạn nữ.
  • Dòng thứ hai chứa ~ n ~ số nguyên ~ a_1, a_2, ..., a_n ~ (1 ≤ ~ a[i] ~ ≤ ~ 10^6 ~) – chiều cao các bạn nam.
  • Dòng thứ ba chứa ~ m ~ số nguyên ~ b_1, b_2, ..., b_m ~ (1 ≤ ~ b[i] ~ ≤ ~ 10^6 ~) – chiều cao các bạn nữ.
Output
  • In ra số lượng cặp khiêu vũ nhiều nhất có thể ghép được.

Ví dụ
Input
5 5
2668 2956 2093 2119 2422
11521 13084 19573 25628 28958
Output
3
Giải thích
  • Sau khi sắp xếp danh sách nam và nữ:
    • Nam: ~ [2093, 2119, 2422, 2668, 2956] ~.
    • Nữ: ~ [11521, 13084, 19573, 25628, 28958] ~.
  • Ghép được các cặp:
    • ~ 2668 ~ với ~ 25628 ~,
    • ~ 2956 ~ với ~ 28958 ~.

Tổng số cặp ghép: 3.




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.

Gửi bài giải
Điểm: 10,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
Tìm kiếm nhị phân
Ngôn ngữ cho phép
C
C++
Java
Kotlin
Pascal
PyPy
Python
Scratch