717 . 大對決

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

aacpschool

User's AC Ratio

100.0% (3/3)

Submission's AC Ratio

100.0% (3/3)

Tags

apcsc apcsc-greedy

Description

小 L 和小 F 是天生的死對頭，他們不管什麼都要進行比較，而近年來圍棋 AI 正夯，於是他們分別訓練了 $N$ 個圍棋 AI 準備來進行一場大對決，雙方各位將自己的 AI 們排好順序，形成 $N$ 場一對一的對決。已知每一台 AI 都有自己的「能力值」，當兩台 AI 進行對戰的時候，總會是能力值比較高的 AI 獲勝，如果雙方的能力值相同則會平手。心機很重的小 L 駭進了小 F 的系統，得到了小 F 所有 AI 的能力值以及排點順序，小 L 希望在這個情況下他能夠贏越多場越好，請幫小 L 計算他至多能夠獲勝幾場。

Input Format

輸入第一行包含一個正整數 $N (1 \leq N \leq 10^ 5)$，代表雙方分別擁有的 AI 數量。
輸入第二行有 $N$ 個正整數 $F_1, F_2, \ldots, F_N (1 \leq F_i \leq 10^ 5)$，代表小 F 的 AI 們的能力值。
輸入第三行有 $N$ 個正整數 $L_1, L_2, \ldots, L_N (1 \leq L_i \leq 10^ 5)$，代表小 L 的 AI 們的能力值。

Output Format

請輸出一個整數代表小 L 的勝場數最大可能值。

Sample Input 1

5
8 7 4 8 3
4 2 5 3 7

Sample Output 1

2

Sample Input 2

5
2 10 6 3 1
3 2 4 6 3

Sample Output 2

3

Hints

Problem Source

AP325

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 0~19 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 524288 65536 1 2
1 1000 524288 65536 1 2
2 1000 524288 65536 2
3 1000 524288 65536 2
4 1000 524288 65536 2
5 1000 524288 65536 2
6 1000 524288 65536 2
7 1000 524288 65536 2
8 1000 524288 65536 2
9 1000 524288 65536 2
10 1000 524288 65536 2
11 1000 524288 65536 2
12 1000 524288 65536 2
13 1000 524288 65536 2
14 1000 524288 65536 2
15 1000 524288 65536 2
16 1000 524288 65536 2
17 1000 524288 65536 2
18 1000 524288 65536 2
19 1000 524288 65536 2
Submit
Back to Top