e070. P-4-14. 控制點(2D-max) - 花中程式設計挑戰系統

Content

平面上有 N 個點，第 i 點的座標為(x[i], y[i])。若 x[i] <= x[j] 且 y[i] <= y[j]，則我們說第 j 點可以控制第 i 點。我們希望能在輸入的點中，選取最少的點做為控制點，使得每一個輸入的點都至少被一個控制點所控制。輸入 N 個點的座標，請計算出最少要選取多少個控制點。以下圖為例，輸入 8 個點中，右上方圈起的四個點即是最少選取的控制點。

Time limit: 1 秒

Input

每筆測試資料的第一行為一個正整數 N，N <= 1e5。第二行有 N 個非負整數，依序是這些點的 X 座標，第三行有 N 個非負整數，依序是這些點的 Y 座標，座標值不超過 1e9。

Output

輸出最少的控制點數量。

Sample Input

範例一：
4
1 2 3 3
1 2 3 3

範例二：
8
3 1 5 3 4 7 8 9
8 2 5 1 2 4 2 3

Sample Output

範例一：
1

範例二：
4

測資資訊：

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

Hint ：

Tags:

掃描線

出處:

AP325 [管理者：

mcjksieu005 (mcjksieu005)

]

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