最小化相邻站点之间的最大距离
给出了
100站。相邻站点之间的距离并不相等。你得到10面旗帜，你必须放置在这些电台。第一旗在第一站，最后一旗在最后一站。现在，将剩下的标志放在最小的位置，使这两个标志之间的总相邻距离最小。
我的方法是：
考虑10个站和4个旗的这个问题，让它们之间的距离为1-----2--3---4----5-----6------7-------8-9---10
其中-表示以单位为单位的距离，即1站与2站之间的距离为5，因此第一站与第十站之间的距离为(5+2+3+4+5+6+7+1+3) = 36。
我们在第一站和第十站之间进行二进制搜索，从而得到36/2 = 18。
因此，我们将选择枢轴作为18单位的距离，并从
(i)第1旗的第1和第18单位距离
(2)第2旗的第19和36单位距离
1旗的平均距离为9，距离第4站的距离越近，我们就会在第4站放置旗子。
平均距离为9，起点距离为27，距离第7站更近，因此我们在7站放置第2旗。
因此，答案将是1-----2--3---4----5-----6------7-------8-9---10，因此最大距离被优化为b/w，在这种情况下，任何两个站都是15，同样，我们可以求解100个站点。
请检查这一方法是否正确或有任何更高的效率。如果我错了，请提前向我表示感谢
回答 1
Stack Overflow用户
发布于 2012-05-29 07:56:01
你的算法错了。在您的示例中，将站点6移动到位置24。你的算法仍然会给出1-4-7-10作为最大距离15的答案，但实际上1-5-6-10会更好，最大距离为14。
http://www.careercup.com/question?id=10680926的多项式时间解(您复制了这个问题，效果很差)具有正确的优点，但远不是最快的答案。下面是这个问题的一个更快的答案。
假设我们从我们愿意使用的最大距离开始。我们可以从第一个站点开始，使用二进制搜索来找到我们愿意跳到的最远的站点，然后搜索到离它最远的位置，等等。使用这种策略，我们可以编写一个函数，该函数取最大输入距离，并告诉我们我们使用了多少个标志。(如果不能这样做，我们就可以报告大量的标志-比如站的数量。)
我们可以把它变成一个函数，输入我们最想要的跳转，它告诉我们我们需要多少个旗子。
现在，我们可以对最小的最大距离进行二进制搜索，给出我们想要的标志的数量。
(您可以通过修改该函数来加快速度，以返回标志的数目，以及最小和最大的输入值，这些值将给出相同的准确答案。额外的两位信息可以用来加速二进制搜索。这给出了我所知道的最快的解决这个问题的方法。
https://stackoverflow.com/questions/10789322
复制相似问题
腾讯云开发者
