複数のポイント間にギャップがある - 最小の最大移動を見つける

Question

PはNのセットを与えられ、各エレメントは実線上のポイントを表します。それらの点の各々において、Pのpに、m(p)石石の積み重ねが置かれる。私たちは、すべての石が最小距離dで分けられているように石を動かしたいと考えています。目標は石が動かされる最大距離を最小にすることです。

例：N = 3点があり、P = {1, 2, 3}があります。 1で

• ようmが定義されている、二つの石（m(1) = 2）、
• が1石（m(2) = 1）、
• と3だ二つの石（m(3) = 2）があります2でそこにいます。
のでように描写することができる

：

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

最小ギャップサイズが2である場合、この例の最適解は、1から0へ

• 動き一石です
• 1石を1から-2に移動する
• 1石を3から4に移動
• は3から任意の石が移動の最大距離は3

  は、残念ながら私は良い方法を考えることができないことを意味するソリューションを

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

  与えます6

に一石を動かしますこの番号を計算し、まだインターネット上で見つけなければならない！ ありがとうございます。

Answer 1

最小距離xを最小にすると、有効な解があるかどうかを簡単に確認できます。 x = floor（max（m）/ 2）* dで始める。

左端の点については、x/dストーンを左側に移動します。 x/d石未満の場合は、すべての石を一番左の可能な点（x、x-dなど）に移動します。 x/d以上の石がある場合は、それらを右に移動します。

2番目の左端の点については、可能な限り多くの点を左に移動し、右に通知します。石を置くことができない場合は、xは有効ではありません。

次のステップは、最適なxをバイナリ検索することです。 xが整数の場合は、log（x）回繰り返す必要があります。

他のオプションは、おそらく、窮状があるときに次の可能な値を推測することです。例：与えられた時点でまだ石がスペースなしで残っている場合は、xを少なくともk/2だけ増やす必要があります。