/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 366 点
問題文
高橋君は引っ越し業者でアルバイトをしています。今日の現場では、N 個の荷物と N 台の台車があります。
荷物 i (1 \leq i \leq N) の重さは W_i であり、台車 j (1 \leq j \leq N) の耐荷重は C_j です。荷物 i を台車 j に載せるには、荷物の重さが台車の耐荷重以下、すなわち W_i \leq C_j でなければなりません。
各台車には荷物を高々 1 つしか載せられず、各荷物も高々 1 台の台車にしか載せられません。台車に載せない荷物や、荷物を載せない台車があっても構いません。
高橋君は、できるだけ多くの荷物を台車に載せて運びたいと考えています。台車に載せて運べる荷物の最大個数を求めてください。
制約
- 1 \leq N \leq 2 \times 10^5
- 1 \leq W_i \leq 10^9 (1 \leq i \leq N)
- 1 \leq C_j \leq 10^9 (1 \leq j \leq N)
- 入力はすべて整数である。
入力
N W_1 W_2 \ldots W_N C_1 C_2 \ldots C_N
- 1 行目には、荷物および台車の個数を表す整数 N が与えられる。
- 2 行目には、各荷物の重さを表す整数 W_1, W_2, \ldots, W_N が空白区切りで与えられる。
- 3 行目には、各台車の耐荷重を表す整数 C_1, C_2, \ldots, C_N が空白区切りで与えられる。
出力
運べる荷物の最大個数を 1 行で出力せよ。
入力例 1
4 3 5 2 8 4 7 1 6
出力例 1
3
入力例 2
7 1 1 1 1 1 1 1 1 1 1 1 1 1 1
出力例 2
7
入力例 3
10 5 12 8 3 15 20 7 1 9 50 10 6 25 2 4 14 8 30 3 11
出力例 3
9
Score : 366 pts
Problem Statement
Takahashi is working a part-time job at a moving company. At today's site, there are N packages and N carts.
The weight of package i (1 \leq i \leq N) is W_i, and the weight capacity of cart j (1 \leq j \leq N) is C_j. To place package i on cart j, the weight of the package must not exceed the weight capacity of the cart, i.e., W_i \leq C_j.
Each cart can hold at most 1 package, and each package can be placed on at most 1 cart. It is acceptable to have packages not placed on any cart, or carts with no packages.
Takahashi wants to load as many packages as possible onto the carts for transport. Find the maximum number of packages that can be loaded onto carts and transported.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 1 \leq W_i \leq 10^9 (1 \leq i \leq N)
- 1 \leq C_j \leq 10^9 (1 \leq j \leq N)
- All inputs are integers.
Input
N W_1 W_2 \ldots W_N C_1 C_2 \ldots C_N
- The first line contains an integer N representing the number of packages and carts.
- The second line contains integers W_1, W_2, \ldots, W_N separated by spaces, representing the weight of each package.
- The third line contains integers C_1, C_2, \ldots, C_N separated by spaces, representing the weight capacity of each cart.
Output
Print the maximum number of packages that can be transported in a single line.
Sample Input 1
4 3 5 2 8 4 7 1 6
Sample Output 1
3
Sample Input 2
7 1 1 1 1 1 1 1 1 1 1 1 1 1 1
Sample Output 2
7
Sample Input 3
10 5 12 8 3 15 20 7 1 9 50 10 6 25 2 4 14 8 30 3 11
Sample Output 3
9