題目亂看= =,以為是 LIS 之類的變形。

題目就是要你找到 比當前暗 且 最遠 的點。

一開始沒什麼想法,後來才想到一個蠻喇的解法= =。

弄一棵像 BSP 的東西,從 最遠 的做回 最近 的點。

BSP 存的是 範圍內 最暗 的暗度。

查詢的話就是 如果左邊比你要查的暗,就往左邊走(因為左邊離你愈遠),否則往右邊走。

當然如果 最大的暗度 < 你的暗度,就是 -1。

一邊查一邊從底部更新上去。

複雜度 O(nlgn)。

我的code http://codepad.org/oHsdUKRW

p.s: 加了 GetInput 才過的,而且大家的code都短短的,應該有比較好的解吧XD。

       這棵 BSP 的結構比較簡單,所以可以簡化減少 CodeLength。 

未簡化的code http://codepad.org/dfSC6Ezq

文章標籤
創作者介紹

jghs1328

jghs1328 發表在 痞客邦 PIXNET 留言(0) 人氣()