lc_hsg9_26_cau4 - Câu 4
Xem dạng PDFTrường THCS A chuẩn bị kỷ niệm 50 năm thành lập trường. Trong buổi kỷ niệm nhà trường có tổ chức một buổi khiêu vũ dạ hội và sẽ mời các thành viên trong câu lạc bộ (CLB) khiêu vũ của trường tham gia. Trong câu lạc bộ khiêu vũ của trường có ~N~ bạn nam và ~M~ bạn nữ đang tích cực tập luyện các điệu nhảy như waltz, minuet, polonaise và quadrille... Để buổi kỷ niệm diễn ra hoàn hảo nhất cô giáo giao cho trưởng CLB khiêu vũ chọn ra một số cặp đôi để tham gia buổi khiêu vũ sao cho kỹ năng khiêu vũ của các đối tác trong mỗi cặp đôi phải chênh lệch không quá ~1~. Với ~N~ bạn nam trong CLB mỗi bạn nam sẽ có kỹ năng khiêu vũ là ~a_i (i = 1,2,3,...,N)~. Và ~M~ bạn nữ trong CLB mỗi bạn nữ sẽ có kỹ năng khiêu vũ là ~b_j (j = 1,2,3,...,M)~.
- Yêu cầu: Hãy lập trình để xác định số lượng cặp đôi tối đa có thể được hình thành từ ~N~ bạn nam và ~M~ bạn nữ trong CLB của trường để tham gia lễ kỷ niệm 50 năm thành lập trường thỏa mãn điều kiện độ chênh lệch về kỹ năng khiêu vũ của các đối tác trong mỗi cặp đôi không quá ~1~.
- Dữ liệu vào:
- Dòng đầu tiên chứa một số nguyên ~N (1 \le N \le 10^5)~ là số lượng các bạn nam trong CLB.
- Dòng thứ hai chứa dãy số ~a_1, a_2, ..., a_N (1 \le a_i \le 10^9)~, trong đó ~a_i~ là kỹ năng khiêu vũ của bạn nam thứ ~i~.
- Dòng thứ ba chứa một số nguyên ~M (1 \le M \le 10^5)~ là số lượng các bạn nữ trong CLB.
- Dòng thứ tư chứa dãy số ~b_1, b_2, ..., b_M (1 \le b_i \le 10^9)~, trong đó ~b_i~ là kỹ năng khiêu vũ của bạn nữ thứ ~i~.
- Kết quả: In ra một số duy nhất là số lượng cặp đôi tối đa có thể được hình thành.
Ví dụ:
Input
4
1 4 6 2
5
5 1 5 7 9
Output
3
Giải thích
Số cặp đôi có thể hình thành tối đa là ~3~ cặp đôi: ~(1, 1); (4, 5); (6, 5)~.
Input
4
4 2 3 6
4
8 9 8 10
Output
0
Giải thích
Không có cặp đôi nào được hình thành thỏa mãn yêu cầu.
Ràng buộc:
- Có ~20\%~ số test ứng với ~1 \le N, M \le 10^3; 0 < a_i, b_j \le 10^6~.
- Có ~80\%~ số test ứng với ~10^4 \le N, M \le 10^5; 10^6 < a_i, b_j \le 10^9~.
Bình luận