作者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