给出了 100 个站点.相邻车站之间的距离不相等。你会得到10面旗帜，你必须把它们放在这些站中。第一面旗帜在第1站，最后一面旗帜在最后一站。现在放置其余标志，使两个标志之间的总相邻距离最小。
我的方法是这样的：
考虑 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 个距离单位，并从
（i） 第一旗的第一和十八距离单位
（二） 第19和第36个距离单位为第2面旗
帜
第一面旗帜的平均距离为9，离第四站更近我们在第 4 站放置旗帜。
平均距离为9，因此从起点的距离为27，更接近第7站因此，我们在第 7 站放置了第二面旗帜。
因此答案将是1-----2--3---4----5-----6------7-------8-9---10因此，最大距离被优化为黑白，在这种情况下，任何两个站都是15同样，我们可以求解 100 个站点
请检查这种方法是否正确，或者是否有更有效的方法。如果我错了，请纠正我提前致谢
你的算法是错误的。 在您的示例中，将工作站 6 移动到位置 24。 您的算法仍然会给出 1-4-7-10 作为最大距离为 15 的答案，但实际上 1-5-6-10 在最大距离为 14 的情况下会更好。
http://www.careercup.com/question?id=10680926 的多项式时间解（你从中复制了这个问题，很糟糕）具有正确的优点，但远非最快的答案。 这是这个问题的更快答案。
假设我们从我们愿意使用的最大距离开始。 我们可以从第一站开始，使用二叉搜索找到我们愿意跳到的最远的车站，然后搜索找到离该站最远的车站，依此类推。 使用此策略，我们可以编写一个函数，该函数采用最大输入距离并告诉我们使用了多少个标志。 （如果做不到，我们可以只报告非常多的标志 - 例如站的数量。
我们可以把它变成一个函数，输入我们愿意采取的最大跳跃，它告诉我们我们需要多少标志。
现在我们可以对最小最大距离进行二进制搜索，从而为我们提供所需的标志数量。
（您可以通过修改该函数以返回标志的数量以及将给出相同确切答案的最小和最大输入值来加快速度。 额外的两位信息可用于加快二进制搜索。 这为这个问题提供了我所知道的最快的解决方案。