作者sorryChen (陈扬和)
看板Programming
标题演算法问题
时间Sun Apr 11 10:57:51 2010
(不好意思post再这里,若应该post再其他版上还请版友告知见谅)
给定n个数选k个数使其中选中的数之间的最短距离最大化
就比如说一个街道上要从n个点中选k个点放垃圾桶
要使最近的两个垃圾桶距离最大化
一开始觉得这个是个简单又典型的问题 但想了两天除了一个O(n^3k)的DP方法
并没有什麽好的解法... 其他一些想法是..头尾都一定会选
如果可以随便放的话L/(k-1)的间隔距离放最好, L 为街道总长
所以若第二个个点大过L/(k-1)则就一定会要选 因为选的时候不会造成瓶颈
但若小於则不一定是最好的 因为可能会造成瓶颈...
不知道版友们能不能指导一下
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 207.151.230.57
※ 编辑: sorryChen 来自: 207.151.230.57 (04/11 10:58)
1F：推 march20:四方是指 n^4? 66.75.255.220 04/11 12:31
2F：→ sorryChen:对阿 n^3 * k 207.151.230.57 04/11 12:59
※ 编辑: sorryChen 来自: 207.151.230.57 (04/11 13:02)
3F：→ askker:给定的n个数字间有规律吗? 220.136.202.45 04/11 13:04
4F：推 yoco315:帮推，想不出来 -,- 118.160.117.43 04/11 13:27
5F：推 march20:看来是个 n*n*k 的表 66.75.255.220 04/11 16:44
6F：推 march20:好像够好了 @@ 66.75.255.220 04/11 16:45
7F：推 march20:咦, 似乎可以少一个 n. 考虑这样的表 66.75.255.220 04/11 16:53
8F：推 march20:T[i,j]=起点为 p0, 终点为 pi 总共选j点 66.75.255.220 04/11 16:55
9F：推 march20:其中最大的最小距离? 66.75.255.220 04/11 16:56
10F：推 march20:T[i,j]=max(1<x<i;min(T[x,j-1],D(x,i))) 66.75.255.220 04/11 17:00
11F：推 march20: = 66.75.255.220 04/11 17:03
12F：推 march20:不过"起点一定会选"看起来是个错的假设@@ 66.75.255.220 04/11 17:05
13F：推 march20:(又想了一下, 拿掉 p0 好像不会怎样) 66.75.255.220 04/11 17:08
14F：推 march20:(所以 k*n^2 应该是可以达成的) 66.75.255.220 04/11 17:11
15F：推 stimim:use binary search might have a O(n lg L) 61.228.152.73 04/11 20:28
16F：→ stimim:algorithm,sorry I can't type chinese now 61.228.152.73 04/11 20:29
17F：→ stimim:where L is the dist. form start to end 61.228.152.73 04/11 20:29
18F：→ stimim: ^^^^ from 61.228.152.73 04/11 20:31
19F：→ sorryChen:非常感谢前辈的回答 我转录了同学的解答 67.152.86.163 04/13 14:19