/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 366 点
問題文
高橋君は、配送センターのマネージャーを務めています。このセンターには N 人の配達員がおり、それぞれ 1 から N の番号が付けられています。各配達員 i には、運搬できる荷物の最大重量 S_i が決まっています。
今日、M 件の配達依頼が届きました。各依頼 j の荷物の重量は D_j です。
高橋君は、配達員たちにできるだけ多くの依頼を割り当てたいと考えています。割り当ては以下のルールに従います。
- 各依頼は高々 1 人の配達員に割り当てられる。どの配達員にも割り当てられない依頼があってもよい。
- 各配達員は高々 1 件の依頼しか担当できない。どの依頼も担当しない配達員がいてもよい。
- 依頼 j を配達員 i に割り当てるには、配達員の最大重量が荷物の重量以上、すなわち S_i \geq D_j でなければならない。
これらのルールに従うすべての割り当て方の中で、割り当てられる依頼の件数の最大値を求めてください。
制約
- 1 \leq N \leq 2 \times 10^5
- 1 \leq M \leq 2 \times 10^5
- 1 \leq S_i \leq 10^9 (1 \leq i \leq N)
- 1 \leq D_j \leq 10^9 (1 \leq j \leq M)
- 入力はすべて整数である。
入力
N M S_1 S_2 \ldots S_N D_1 D_2 \ldots D_M
- 1 行目には、配達員の人数 N と依頼の件数 M が、スペース区切りで与えられる。
- 2 行目には、各配達員が運搬できる最大重量 S_1, S_2, \ldots, S_N が、スペース区切りで与えられる。
- 3 行目には、各依頼の荷物の重量 D_1, D_2, \ldots, D_M が、スペース区切りで与えられる。
出力
割り当てられる依頼の件数の最大値を 1 行で出力せよ。
入力例 1
3 3 5 3 8 4 6 2
出力例 1
3
入力例 2
3 3 1 2 3 10 20 30
出力例 2
0
入力例 3
10 8 2 5 8 1 10 3 7 6 4 9 3 6 1 8 5 11 7 2
出力例 3
7
入力例 4
15 12 14 3 7 25 11 9 30 5 18 2 22 8 16 12 20 6 10 15 28 4 19 13 1 24 17 21 35
出力例 4
11
入力例 5
1 1 1 1
出力例 5
1
Score : 366 pts
Problem Statement
Takahashi is the manager of a delivery center. The center has N delivery workers, numbered from 1 to N. Each delivery worker i has a maximum weight S_i that they can carry.
Today, M delivery requests have arrived. The weight of the package for each request j is D_j.
Takahashi wants to assign as many requests as possible to the delivery workers. The assignment must follow these rules:
- Each request is assigned to at most 1 delivery worker. Some requests may remain unassigned.
- Each delivery worker can handle at most 1 request. Some delivery workers may not handle any request.
- To assign request j to delivery worker i, the delivery worker's maximum weight must be at least the weight of the package, i.e., S_i \geq D_j.
Among all assignments that follow these rules, find the maximum number of requests that can be assigned.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 1 \leq M \leq 2 \times 10^5
- 1 \leq S_i \leq 10^9 (1 \leq i \leq N)
- 1 \leq D_j \leq 10^9 (1 \leq j \leq M)
- All input values are integers.
Input
N M S_1 S_2 \ldots S_N D_1 D_2 \ldots D_M
- The first line contains the number of delivery workers N and the number of requests M, separated by a space.
- The second line contains the maximum weights S_1, S_2, \ldots, S_N that each delivery worker can carry, separated by spaces.
- The third line contains the package weights D_1, D_2, \ldots, D_M for each request, separated by spaces.
Output
Print the maximum number of requests that can be assigned, on a single line.
Sample Input 1
3 3 5 3 8 4 6 2
Sample Output 1
3
Sample Input 2
3 3 1 2 3 10 20 30
Sample Output 2
0
Sample Input 3
10 8 2 5 8 1 10 3 7 6 4 9 3 6 1 8 5 11 7 2
Sample Output 3
7
Sample Input 4
15 12 14 3 7 25 11 9 30 5 18 2 22 8 16 12 20 6 10 15 28 4 19 13 1 24 17 21 35
Sample Output 4
11
Sample Input 5
1 1 1 1
Sample Output 5
1