Khiêu vũ
View as PDF
Submit solution
Points:
200.00 (partial)
Time limit:
1.0s
Memory limit:
1G
Input:
stdin
Output:
stdout
Author:
Problem type
Allowed languages
C, C++, GAS64, Pascal, Perl, PHP, Python, Sed, TCL, Text
Một làng quê có ~m~ chàng trai đánh số từ 1 tới ~m~ và ~n~ cô gái đánh số từ 1 tới ~n~. Chàng trai thứ i có chiều cao ~a_i~(~i = 1,2,…,m~), cô gái thứ ~j~ có chiều cao ~b_j~(~j = 1,2,…n~). Trong một buổi khiêu vũ, người ta muốn chọn ra một số cặp nhảy. Mỗi cặp nhảy gồm đúng 1 chàng trai và 1 cô gái và trong cặp đó, chàng trai phải cao hơn cô gái. Mỗi chàng trai, cô gái trong làng không được tham gia quá 1 cặp nhảy.
Yêu cầu: Tìm một số nhiều nhất các cặp nhảy thỏa mãn yêu cầu trên.
Dữ liệu vào:
- Dòng 1 chứa hai số nguyên dương ~m~, ~n~
- Dòng 2 chứa ~m~ số nguyên dương ~a_1~, ~a_2~,…, ~a_m~
- Dòng 3 chứa ~n~ số nguyên dương ~b_1~, ~b_2~,…, ~b_n~
Giới hạn:
- ~n,m <=~ ~10^5~
- Giá trị các phần tử trong hai mảng ~a, b~ có trị tuyệt đối không vượt quá ~10^9~
Kết quả:Một số nguyên duy nhất là số cặp nhảy theo phương án tìm được.
Ví dụ:
Input 1:
3 2
1 2 3
2 3
Output 1:
1
Loading...