最小化任何相邻站之间的最大距离

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（你复制这个问题，很糟糕，从）具有正确的优点，但远不是最快的答案。对于这个问题，这是一个更快的答案。

假设我们从我们愿意使用的最大距离开始。我们可以从第一个站点开始，使用二分查找找到我们愿意跳到的最远的站点，然后搜索找到距离该站点最远的站点等。使用这种策略，我们可以编写一个函数，该函数获取最大输入距离并告诉我们使用了多少个标志。 （如果不能完成，我们可以报告大量的标志 - 例如站点数量。）

我们可以把它变成一个函数，输入我们愿意采取的最大跳跃它告诉我们需要多少个标志。

现在我们可以对最小的最大距离进行二进制搜索，从而为我们提供所需的标志数量。 （你可以通过修改该函数来返回标志的数量，以及最小和最大的输入值，以得到相同的确切答案，这可以加快速度。额外的两位信息可以用来加速二进制搜索。这给出了我所知道的这个问题的最快解决方案。）