題目大意:給定猴山各個猴子的坐標(X,Y),找出滿足不存在其他猴子在X軸坐標和Y軸坐標同時大於或等於的猴子數量
我們先來看看,當一個點的坐標(X,Y)大於另外一個點(X0,Y0)在坐標軸下的情況,如下圖:
可以看出當一個點X > X0 且 Y > Y0,則可以看出(X0,Y0)在點(X,Y)與坐標軸圍成的矩形的投影范圍內。
下面擴展到一般情況:
如下圖所示,所有可能成為猴王的點會在最外圍形成“階梯”,如果從右向左掃描,用一個變量保存當前階梯的“高度”,如果當前點的高度小於階梯高度,則此點必在其它點的陰影中,如果當前點的高度大於階梯的高度,那麼將計數器遞增並更新階梯的高度為新點的高度。需要留意的是x坐標或者y坐標相等的情形。將點排序復雜度為O(nlogn),掃描一遍為O(n),最後的時間復雜度為O(nlogn)。
更多源碼,點擊http://www.51ojr.com/report/full/36