close
表面上是需要O(N^2)的
如果你仔細分析問題
你就會發現其實就是從後面找回來
然後該狀態下找第n大的數字
這樣的話就用Ranking Tree (我不確定真正的名稱 這是我對這作法的命名)
可以在log maxL的時間下找到要的數字
這樣時間可以縮到O(N log N)
以這樣的規模就算合理了
如果他的N再大到50000(跟UVA ACM某題一樣)
那就不太可能用O(N^2)了
全站熱搜
- Jul 27 Mon 2009 11:44
PKU - 2182 Lost Cows
留言列表
留言列表發表留言
