最小総移動距離

2463。最小総移動距離

難易度: 難しい

トピック: 配列、動的プログラミング、ソート

X 軸にはいくつかのロボットと工場があります。整数配列ロボットが与えられます。ここで、 robot[i] は i ^番目 ロボットの位置です。また、2D 整数配列ファクトリーも与えられます。ここで、factory[j] = [position_j, limit_j] は、position_j が j の位置であることを示します。 _番目の工場と、j_番目の工場は最大でも_j台のロボットを修理できるとのこと。

各ロボットの位置はユニークです。各工場の立場も独特です。ロボットは最初は工場と同じ位置にあることができることに注意してください。

すべてのロボットは最初は壊れています。彼らは一方向に進み続けます。方向は、X 軸の負の方向または正の方向になります。ロボットが限界に達していない工場に到達すると、工場はロボットを修理し、ロボットは動きを停止します。

いつでも、一部 ロボットの最初の移動方向を設定できます。あなたの目標は、すべてのロボットの総移動距離を最小限に抑えることです。

すべてのロボットが移動した最小合計距離を返します。テスト ケースは、すべてのロボットを修復できるように生成されます。

次のことに注意してください

• すべてのロボットは同じ速度で動きます。
• 2 台のロボットが同じ方向に移動した場合、衝突することはありません。
• 2 台のロボットが反対方向に移動し、ある時点で出会った場合、それらは衝突しません。それらは互いに交差します。
• ロボットが限界に達した工場の前を通過すると、まるで存在しないかのように工場を横切ります。
• ロボットが位置 x から位置 y に移動した場合、移動距離は |y - x| です。

例 1:

• 入力: ロボット = [0,4,6]、ファクトリー = [[2,2],[6,2]]
• 出力: 4
• 説明: 図に示すように:
  • 位置 0 の最初のロボットが正の方向に移動します。第一工場での修理となります。
  • 位置 4 の 2 番目のロボットが負の方向に移動します。第一工場での修理となります。
  • 位置 6 にある 3 番目のロボットは、第 2 工場で修理されます。移動する必要はありません。
  • 最初の工場の制限は 2 で、2 つのロボットが固定されました。
  • 第 2 工場の制限は 2 台で、ロボットは 1 台固定されました。
  • 合計距離は |2 - 0| です。 |2 - 4| |6 - 6| = 4. 4 よりも優れた合計距離を達成することはできないことがわかります。

例 2:

• 入力: ロボット = [1,-1]、ファクトリー = [[-2,1],[2,1]]
• 出力: 2
• 説明: 図に示すように:
  • 位置 1 の最初のロボットが正の方向に移動します。第二工場での修理となります。
  • 位置 -1 にある 2 番目のロボットは負の方向に移動します。第一工場での修理となります。
  • 最初の工場の制限は 1 で、1 つのロボットを固定しました。
  • 第 2 工場の制限は 1 で、ロボットを 1 台固定しました。
  • 合計距離は |2 - 1| です |(-2) - (-1)| = 2. 2 よりも優れた合計距離を達成することはできないことがわかります。

制約:

• 1
• factory[j].length == 2
• -10⁹ <= ロボット[i]、位置 j <= 10⁹
• 0 <= 制限_j <= robot.length
• 入力は、すべてのロボットを常に修復できるように生成されます。

ヒント:

1. ロボットと工場を位置ごとに並べ替えます。
2. 分類後、各工場がロボットの一部のサブセグメントを修理する必要があることに注意してください。
3. 最初の i 個のロボットと最初の j 個の工場を修理するための最小合計距離を見つけます。

解決策:

ソートされたロボットとファクトリー配列を使用して動的プログラミングを使用できます。その考え方は、各工場の修理能力を尊重し、各ロボットが工場で修理するために移動しなければならない距離を最小限に抑えることです。このアプローチを段階的に詳しく説明します:

1. ロボットとファクトリー配列を位置で並べ替えます。並べ替えると、近くのロボットを近くの工場に割り当てることができるため、移動距離を最小限に抑えることができます。

2. 動的プログラミング手法: 2D DP テーブル dp[i][j] を定義します。ここで:

   • i は最初の i ロボットを表します。
   • j は最初の j 個のファクトリーを表します。
   • dp[i][j] には、これらの j 個のファクトリーを使用してこれらの i 個のロボットを修理するための最小合計距離が格納されます。

3. 状態遷移:

   • 各工場について、制限内で連続するロボットのサブセットを修復してみます。
   • 位置 p にある工場 j について、各ロボットから工場の位置までの距離を合計することで、それに k 台のロボットを割り当てるために必要な最小距離を計算します。
   • 修理するロボットの数を減らすか、工場の能力を最大限に活用するかの最小値を選択して、DP の状態を更新します。

このソリューションを PHP で実装してみましょう: 2463。最小総移動距離

  
  
  説明：




並べ替え: 近くのロボットを近くの工場に確実に割り当てるために、ロボットと工場を位置によって並べ替えます。

DP 初期化: どの工場でもロボットが修理されていないということは距離がゼロであることを意味するため、dp[0][0] = 0 を初期化します。

動的プログラミングの移行:


各工場 j について、その制限内で先行する k 個のロボットの修理を試みます。
合計距離は sumDist に累積されます。
k 台のロボットを修復した後、距離と以前の状態を考慮して dp[i][j] を最小値で更新します。








  
  
  複雑




時間計算量: O(n * m * L) ここで、n はロボットの数、m は工場の数、L は工場が処理できる修理の上限です。

空間複雑度: DP テーブルの O(n * m)。


このソリューションは、工場出荷時の制限内で修理されるすべてのロボットの最小移動距離を効率的に計算します。

連絡先リンク

このシリーズが役立つと思われた場合は、GitHub で リポジトリ にスターを付けるか、お気に入りのソーシャル ネットワークで投稿を共有することを検討してください。あなたのサポートは私にとって大きな意味を持ちます!

このような役立つコンテンツがさらに必要な場合は、お気軽にフォローしてください:


LinkedIn
GitHub



          

            
  

            
        
以上が最小総移動距離の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。