Khiêu vũ
Xem dạng PDFMô 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
Gửi bài giải
Kotlin
PyPy
Đ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
Pascal
Python
Scratch