100 駅 。隣接する駅間の距離が等しくありません。これらのステーションの間に配置する必要がある 10 個のフラグが与えられます。最初の旗は最初の駅にあり、最後の旗は最後の駅にあります。次に、残りのフラグを、2 つのフラグ間の合計隣接距離が最小になるように配置します。
私のアプローチはこれです：
この問題を 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 番目の単位
距離の平均は、第 4 ステーションに近い第 1 フラグの場合、第 4 ステーションにフラグを配置します。
距離の平均は 9 であるため、開始からの距離は 27 であり、7 番目の駅に近いため、2 番目のフラグを 7 番目の駅に配置します。
したがって、答えは 1 ------ 2--3--- 4 ----5-----6------ 7 -------8-9--- 10になります。 したがって、この場合、任意の 2 つのステーションの b/w は 15 であるため、最大距離は最適化されます。同様に、100 ステーションについて解くことができます。
このアプローチが正しいかどうか、またはより効率的な方法があるかどうかを確認してください。間違っていたら訂正してください よろしくお願いします