程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> 關於C語言 >> POJ 1828 解題報告

POJ 1828 解題報告

編輯:關於C語言

問題翻譯


     題目大意:給定猴山各個猴子的坐標(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

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved