Re: [問題] 第 k 大連續子陣列和
看板Prob_Solve (計算數學 Problem Solving)作者FRAXIS (喔喔)時間9年前 (2015/03/06 22:38)推噓0(0推 0噓 0→)留言0則, 0人參與討論串5/5 (看更多)
我在思考樹上的 k 大路徑時找到了一個比較容易做的o(n^2)方法。
（bzoj 3784）
用陣列的中點把陣列切成兩半，計算通過中點的子陣列和，然後分別遞迴
兩邊計算不通過中點的子陣列和，就可以找到第 k 大了。
計算通過中點的子陣列和時，
把左半邊每個元素到中點的子陣列和算出並排序，設為X。
把右半邊每個元素到中點的子陣列和算出並排序，設為Y。
通過中點的子陣列和就可以被表示成 X + Y 了，是一個行與列都排好序的矩陣。
總共會有O(n lg n)個有序矩陣，在裡面找出第 k 大可以在O(n lg^2 n)完成。
（理論上是可以O(n lg n)的，但是應該不實用）
同樣的技巧可以解樹上第 k 大路徑，O(n lg^2 n)或是O(n lg n)。
也可以解樹上 p-center（當然也可以解 path 上的 p-center）
樹上的 p-center 有四種變化：V/V/p, V/E/p, E/V/p, E/E/p。
前三者可以在O(n lg^2 n)內解出，第四個是O(pn lg^2n)
（理論上可以在O(n)和O(n lg^2n)解出）
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 129.170.195.149
※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1425652727.A.9F3.html
討論串 (同標題文章)
完整討論串 (本文為第 5 之 5 篇)：
2
11
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
