小编And*_*nes的帖子

我们给出了一组P大小N,每个元素代表实线上的一个点.在每个点p上P,m(p)放置一堆石头石头.我们想要移动石头使它们全部分开最小距离d,目标是尽量减少任何石头移动的最大距离.

示例:N = 3有点,和P = {1, 2, 3}.m是这样定义的

• 在1,有两块石头(m(1) = 2),
• 在2有一块石头(m(2) = 1),
• 3有两块石头(m(3) = 2).

这可以像这样描绘:

      o     o
      o  o  o
 ----------------
...0  1  2  3  4...

如果最小间隙大小为2,则此示例的最佳解是

• 将一块石头从1移动到0
• 将一块石头从1移动到-2
• 从3到4移动一块石头
• 从3到6移动一块石头

这提供了一个解决方案

    o     o     o     o     o
 ------------------------------
...-2 -1  0  1  2  3  4  5  6...

这意味着任何石头的最大行进距离为3.

不幸的是,我想不出一个很好的方法来计算这个数字,还没有在互联网上找到一个!先感谢您.