Phân phối căn hộ
Xem dạng PDFMô tả bài toán:
Có ~ n ~ người xin thuê căn hộ và ~ m ~ căn hộ trống. Nhiệm vụ của bạn là phân phối các căn hộ sao cho số người thuê được căn hộ là nhiều nhất có thể.
Mỗi người thuê có một kích thước căn hộ mong muốn và sẽ chấp nhận bất kỳ căn hộ nào có kích thước nằm trong khoảng từ ~ x - k ~ đến ~ x + k ~ (với ~ x ~ là kích thước mong muốn và ~ k ~ là sai số cho phép).
Input:
- Dòng đầu tiên chứa ba số nguyên ~ n, m, k ~: số người xin thuê, số căn hộ trống, và sai số cho phép.
- Dòng thứ hai chứa ~ n ~ số nguyên ~ a_1, a_2, \dots, a_n ~: kích thước căn hộ mong muốn của từng người xin thuê.
- Dòng thứ ba chứa ~ m ~ số nguyên ~ b_1, b_2, \dots, b_m ~: kích thước của từng căn hộ.
Output:
- In ra một số nguyên: số người thuê được căn hộ.
Ràng buộc:
- ~ 1 \leq n, m \leq 2 \times 10^5 ~
- ~ 0 \leq k \leq 10^9 ~
- ~ 1 \leq a_i, b_i \leq 10^9 ~
Ví dụ:
Input:
4 3 5
60 45 80 60
30 60 75
Output:
2
Giải thích:
- Người 1 (60) có thể chọn căn hộ ~ 60 ~.
- Người 3 (80) có thể chọn căn hộ ~ 75 ~.
- Tổng số người thuê được căn hộ là 2.
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
Nguồn bài:
CSES
Dạng bài
CSES
Ngôn ngữ cho phép
C
C++
Java
Pascal
Python
Scratch