我们给出了一组P大小N,每个元素代表实线上的一个点.在每个点p上P,m(p)放置一堆石头石头.我们想要移动石头使它们全部分开最小距离d,目标是尽量减少任何石头移动的最大距离.
示例:N = 3有点,和P = {1, 2, 3}.m是这样定义的
m(1) = 2),m(2) = 1),m(3) = 2).这可以像这样描绘:
o o
o o o
----------------
...0 1 2 3 4...
如果最小间隙大小为2,则此示例的最佳解是
这提供了一个解决方案
o o o o o
------------------------------
...-2 -1 0 1 2 3 4 5 6...
这意味着任何石头的最大行进距离为3.
不幸的是,我想不出一个很好的方法来计算这个数字,还没有在互联网上找到一个!先感谢您.
给定最小最大距离 x，很容易检查是否存在有效的解决方案。从 x = 楼层(max(m)/2)*d 开始。
对于最左边的点，向左移动 x/d 颗棋子。如果棋子少于 x/d，则将所有棋子移动到最左边的可能点（x、xd 等）。如果有超过 x/d 个棋子，请将它们移到右侧。
对于第二个最左边的点，将尽可能多的点向左移动，并向右移动提醒，依此类推。如果在任何时候都无法放置棋子，则 x 无效。
下一步是执行二分搜索以获得最佳 x。如果 x 是整数，则需要重复此操作 log(x) 次。
另一种选择是在出现僵局时推断下一个可能的值。示例：在给定点，如果仍有 k 个石头没有空间，则可能需要将 x 增加至少 k/2。