最小化任何相鄰站之間的最大距離

Question

給出100個站。相鄰電臺之間的距離不相等。你得到10個旗幟，你必須在這些車站之間放置。第一個標誌位於第一個車站，最後一個標誌位於最後一個車站。現在放置其餘標誌，使兩個標誌之間的總相鄰距離最小。

我的做法是這樣的：

考慮這個問題了10臺和4個標誌 讓他們之間的距離是爲 1 ----- 2--3 --- 4-- --5 ----- 6 ------ 7 ------- 8-9 --- 10

其中 - 代表距離單位 它表示第一和第二之間的距離站是5, 因此，第一站和第十站之間的距離將是（5 + 2 + 3 + 4 + 5 + 6 + 7 + 1 + 3） = 36

我們應用第1次和第10站之間的二進制搜索，因此我們得到36/2 = 18

因此，我們會選擇樞軸18單位距離的和

（一）申請二進制搜索第一和距離的18單元，用於第一標記

（ⅱ）19和用於第二標誌距離的第36單元

距離的

平均爲9 1 ST標誌哪個更接近第四站 我們把標誌站4.

距離的平均爲9，因此距離開始是27，其是更接近第七站 因此我們把第二標誌站7上。

因此回答將是 ----- --- 2--3 4 ---- 5 ----- ------ 6 7 --- ---- 8-9 --- 因此，最大距離優化爲b/w，在這種情況下，任意兩個站都是15， 同樣，我們可以解決100個工作站

請檢查此方法是否正確或可以有更高效。 糾正我，如果我錯了 在此先感謝

Answer 1

你的算法是錯誤的。在你的例子中，移動站6到位置24.你的算法仍然會給1-4-7-10作爲最大距離爲15的答案，但實際上1-5-6-10會更好，最大距離的

多項式時間解決方案http://www.careercup.com/question?id=10680926（你複製這個問題，很糟糕，從）具有正確的優點，但遠不是最快的答案。對於這個問題，這是一個更快的答案。

假設我們從我們願意使用的最大距離開始。我們可以從第一個站點開始，使用二分查找找到我們願意跳到的最遠的站點，然後搜索找到距離該站點最遠的站點等。使用這種策略，我們可以編寫一個函數，該函數獲取最大輸入距離並告訴我們使用了多少個標誌。 （如果不能完成，我們可以報告大量的標誌 - 例如站點數量。）

我們可以把它變成一個函數，輸入我們願意採取的最大跳躍它告訴我們需要多少個標誌。

現在我們可以對最小的最大距離進行二進制搜索，從而爲我們提供所需的標誌數量。 （你可以通過修改該函數來返回標誌的數量，以及最小和最大的輸入值，以得到相同的確切答案，這可以加快速度。額外的兩位信息可以用來加速二進制搜索。這給出了我所知道的這個問題的最快解決方案。）