Buổi khiêu vũ BerSU
Đề bài
Mô tả
Có chàng trai và cô gái tham gia một buổi khiêu vũ. Mỗi người có một chỉ số kỹ năng nhảy. Ta muốn ghép các cặp nhảy, mỗi cặp gồm một chàng trai và một cô gái, sao cho chênh lệch kỹ năng nhảy giữa hai người trong cặp không vượt quá .
Mỗi người chỉ được tham gia nhiều nhất một cặp. Hãy xác định số cặp nhảy lớn nhất có thể tạo thành.
Dữ liệu vào
- Dòng thứ nhất chứa số nguyên — số chàng trai.
- Dòng thứ hai chứa số nguyên — kỹ năng nhảy của các chàng trai.
- Dòng thứ ba chứa số nguyên — số cô gái.
- Dòng thứ tư chứa số nguyên — kỹ năng nhảy của các cô gái.
Dữ liệu ra
In ra một số nguyên duy nhất — số cặp nhảy lớn nhất có thể tạo thành.
Ràng buộc
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 4 1 4 6 2 5 5 1 5 7 9 |
3 | Có thể ghép: chàng trai kỹ năng 1 với cô gái kỹ năng 1, chàng trai kỹ năng 4 với cô gái kỹ năng 5, chàng trai kỹ năng 6 với cô gái kỹ năng 5. Được cặp. |
| 4 1 2 3 4 4 10 11 12 13 |
0 | Mọi chàng trai đều có kỹ năng , mọi cô gái đều có kỹ năng , chênh lệch luôn lớn hơn nên không ghép được cặp nào. |
| 5 1 1 1 1 1 3 1 2 3 |
2 | Hai cô gái kỹ năng 1 và 2 đều ghép được với chàng trai kỹ năng 1; cô gái kỹ năng 3 chênh lệch nên không ghép được. Được cặp. |
Bình luận