※ [本文轉錄自 sorryChen 信箱] 作者: forken (forken) 標題: Re: 演算法問題 時間: Mon Apr 12 03:06:49 2010 ※ 引述《sorryChen (陳揚和)》之銘言： : (不好意思post再這裡,若應該post再其他版上還請版友告知見諒) : 給定n個數選k個數使其中選中的數之間的最短距離最大化 : 就比如說一個街道上要從n個點中選k個點放垃圾桶 : 要使最近的兩個垃圾桶距離最大化 : 一開始覺得這個是個簡單又典型的問題 但想了兩天除了一個O(n^3k)的DP方法 : 並沒有什麼好的解法... 其他一些想法是..頭尾都一定會選 : 如果可以隨便放的話L/(k-1)的間隔距離放最好, L 為街道總長 : 所以若第二個個點大過L/(k-1)則就一定會要選 因為選的時候不會造成瓶頸 : 但若小於則不一定是最好的 因為可能會造成瓶頸... : 不知道版友們能不能指導一下 哈囉!揚和, 我是效飛, 我想這個問題應該可以在用類似 binary search 的方式 在 O(n log n) 解決, Preprocessing: 先把 n 個數 sorting into (a1, a2,..., an) Verification: 考慮如果給一個 value s， 我們要如何在 O(n) 驗證是否有一種選法, 可以使得 max min {任兩個選中的數} >= s? 首先 a1 一定要選，所以設 b1 := a1, 第二個數 b2 := min ai such that ai-b1>=s 第三個數 b3 := min ai such that ai-b2>=s ... 依此類推 如果到 bk 都存在，則表示{b1,...bk} 為一種選法， 可使得 max min{任兩個選中的數} >= s。 反之如果某個 bi 不存在， 則表示不存在一種選法使得 max min{任兩個選中的數} >= s。 Search: 我們知道如何驗證是否有一種選法， 可以使得 max min{任兩個選種的數} >=s， 剩下的問題就是找到最大的 s。 總共有大約 n^2 個可能的 s， 所以用 binary search 總共會有 log (n^2) = O(log n) 個 iterations， 每個 iteration 所需的驗證時間是 O(n)，所以總共的時間是 O(n log n)。 ------------------------------------------------------------------- 但還存在一個問題， 就是我們如何在所有可能的 s 中進行 binary search? (如果真的把所有可的 s 都列出，時間至少就是 Omega(n^2)) 這可以利用 Cartesion Sum selection 做到， 關於 Cartesion Sum selection 可以參考: "Selection in X + Y and matrices with sorted rows and columns"。 IPL, Volume 20, Issue 1, 2 January 1985, 這個方法不是很漂亮，畢竟還是利用到 cartesian sum selection， 但應該可以解決你的問題。 如果對 complexity 要求不那麼嚴格，也可以把所有 n^2 種 s 都列出， 做 sorting 後進行 binary search， 這樣時間就變成 O(n^2 log n) --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 122.126.169.230 --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 207.151.231.39