※ [本文转录自 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