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...