a096. P_4_14 控制點(2D-max)

Content

平面上有N個點，第i點的座標為(x[i], y[i])。若 x[i] $\leq$ x[j] 且 y[i] $\leq$ y[j]，則我們說第j點可以控制第i點。我們希望能在輸入的點中，選取最少的點做為控制點，使得每一個輸入的點都至少被一個控制點所控制。輸入N個點的座標，請計算出最少要選取多少個控制點。

Input

每筆測試資料的第一行為一個正整數 $N$，$N \leq 10^5$。第二行有 $N$ 個非負整數，依序是這些點的X座標，第三行有 $N$ 個非負整數，依序是這些點的Y座標，座標值不超過$10^9$。

Output

輸出最少的控制點數量。

Sample Input #1

4
1 2 3 3
1 2 3 3

Sample Output #1

Sample Input #2

8
3 1 5 3 4 7 8 9
8 2 5 1 2 4 2 3

Sample Output #2

測資資訊：

記憶體限制： 512 MB
公開測資點#0 (20%): 1.0s , <10M
公開測資點#1 (20%): 1.0s , <10M
公開測資點#2 (20%): 1.0s , <10M
公開測資點#3 (20%): 1.0s , <10M
公開測資點#4 (20%): 1.0s , <10M

Hint ：

Tags:

ch4

出處:

Prof.Wu [管理者： s710426(?0_o)//) ]

ID	User	Problem	Subject	Hit	Post Date
沒有發現任何「解題報告」