切換
舊版
前往
大廳
主題

ZeroJudge - d555: 平面上的極大點 解題心得

Not In My Back Yard | 2019-01-13 17:45:37 | 巴幣 0 | 人氣 365

題目連結:


題目大意:
給定一正整數 N (1 ≦ N ≦ 500, 000),代表接下來有 N 列。每一列有兩正整數 x 、 y (0 ≦ x、y ≦ 100, 000),代表一個二維空間中的點之座標。

而我們定義點 A (A, A)支配(Dominate)點 B (B, B),如果
≧ B 且 A ≧ B
簡言之,點 A 在點 B 的右上角。

求有多少點沒有被支配(沒有點在自己的右邊、上面以及右上方),按照 x 座標由小到大輸出,格式按照範例輸出。



範例輸入:
11
0 8
1 10
3 4
4 6
4 9
5 8
6 9
7 5
8 7
9 8
10 6



範例輸出:
Case 1:
Dominate Point:
4
(1,10)
(6,9)
(9,8)
(10,6)



解題思維:
不難看出,最右邊(x 座標最大)的點一定不會被支配(因為絕對不會有點在其右邊)。但是如果最右邊的有很多個點,就取 y 座標最大的那個點,那個點才會是題目所要的。

當取好了第一個不會被支配的點後,我們可以得知接下來要挑的點之 y 座標一定會大於現在的點。


我們可以先對 x 軸排序,再對 y 軸排序(兩者都是由大到小排)。這樣子儲存點的陣列之第一個位置即是我們要挑的第一個點。再來遞增陣列的索引值,碰到比之前的 y 軸值還大的第一個點,即是下一個我們要挑的點。跑到陣列結尾,就挑完所有的點了。

最後,按照 x 座標由小到大輸出以及輸出格式即可。

此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作