2

给出了 100 个站点。相邻站之间的距离不相等。您将获得 10 个标志，您必须在这些站点中放置这些标志。第一个标志在第一个站，最后一个标志在最后一个站。现在放置剩余的标志，使两个标志之间的总相邻距离最小。

我的方法是这样的：

考虑这个问题 10 个站和 4 个标志让它们之间的距离为 1-----2--3---4----5-----6--------7-- -----8-9---10

式中-代表距离单位表示第1站和第2站的距离为5，因此第1站和第10站的距离为(5+2+3+4+5+6+7+1+3) = 36

我们在第 1 站和第 10 站之间应用二进制搜索，因此我们得到 36/2 = 18

因此，我们将选择枢轴作为 18 个距离单位并应用二进制搜索

(i) 第 1 旗的第 1 和第 18 距离单位

(ii) 第 2 旗的第 19 和第 36 距离单位

1st flag 的平均距离为 9，更接近于 4th 站，我们将 flag 放置在 4 站。

平均距离为 9，因此距起点的距离为 27，更接近第 7 站因此我们在第 7 站放置第二个标志。

因此答案将是 1 -----2--3--- 4 ----5-----6------ 7 --------8-9--- 10 因此，在这种情况下，最大距离被优化为 b/w 任意两个站点为 15 类似地，我们可以求解 100 个站点

请检查这种方法是否正确，或者是否有更有效的方法。如果我错了，请纠正我提前谢谢

4

1 回答 1

0

你的算法是错误的。在您的示例中，将站 6 移动到位置 24。您的算法仍然会给出 1-4-7-10 作为最大距离 15 的答案，但实际上 1-5-6-10 会更好，最大距离14。

http://www.careercup.com/question?id=10680926上的多项式时间解决方案（您复制了这个问题，很糟糕，来自）具有正确的优点，但远非最快的答案。这是此问题的更快答案。

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

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

现在我们可以对最小的最大距离进行二分搜索，从而得到我们想要的标志数量。

（您可以通过修改该函数以返回标志的数量以及将给出相同确切答案的最小和最大输入值来加快这一速度。额外的两位信息可用于加速二进制搜索。这给出了我知道这个问题的最快解决方案。）

于 2012-05-29T07:56:01.810 回答