P-4-14. 控制點 (2D-max)


Submit solution

分數: 100 (partial)
時間限制: 1.0s
記憶體限制: 1G

作者:
題目類型
允許的語言
Assembly, Brainfuck, C, C++, Python

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

輸入格式

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

輸出格式

輸出最少的控制點數量。

範例輸入一

4
1 2 3 3
1 2 3 3

範例輸出一

1

範例輸入一

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

範例輸出一

4

評論

目前沒有評論。