给出了 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 个站点
请检查这种方法是否正确,或者是否有更有效的方法。如果我错了,请纠正我提前谢谢