2463。最小総移動(dòng)距離

難易度: 難しい

トピック: 配列、動(dòng)的プログラミング、ソート

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

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

すべてのロボットは最初は壊れています。彼らは一方向に進(jìn)み続けます。方向は、X 軸の負(fù)の方向または正の方向になります。ロボットが限界に達(dá)していない工場(chǎng)に到達(dá)すると、工場(chǎng)はロボットを修理し、ロボットは動(dòng)きを停止します。

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

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

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

• すべてのロボットは同じ速度で動(dòng)きます。
• 2 臺(tái)のロボットが同じ方向に移動(dòng)した場(chǎng)合、衝突することはありません。
• 2 臺(tái)のロボットが反対方向に移動(dòng)し、ある時(shí)點(diǎn)で出會(huì)った場(chǎng)合、それらは衝突しません。それらは互いに交差します。
• ロボットが限界に達(dá)した工場(chǎng)の前を通過(guò)すると、まるで存在しないかのように工場(chǎng)を橫切ります。
• ロボットが位置 x から位置 y に移動(dòng)した場(chǎng)合、移動(dòng)距離は |y - x| です。

例 1:

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

例 2:

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

制約:

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

ヒント:

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

解決策:

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

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

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

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

3. 狀態(tài)遷移:

   • 各工場(chǎng)について、制限內(nèi)で連続するロボットのサブセットを修復(fù)してみます。
   • 位置 p にある工場(chǎng) j について、各ロボットから工場(chǎng)の位置までの距離を合計(jì)することで、それに k 臺(tái)のロボットを割り當(dāng)てるために必要な最小距離を計(jì)算します。
   • 修理するロボットの數(shù)を減らすか、工場(chǎng)の能力を最大限に活用するかの最小値を選択して、DP の狀態(tài)を更新します。

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

  
  
  説明：




並べ替え: 近くのロボットを近くの工場(chǎng)に確実に割り當(dāng)てるために、ロボットと工場(chǎng)を位置によって並べ替えます。

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

動(dòng)的プログラミングの移行:


各工場(chǎng) j について、その制限內(nèi)で先行する k 個(gè)のロボットの修理を試みます。
合計(jì)距離は sumDist に累積されます。
k 臺(tái)のロボットを修復(fù)した後、距離と以前の狀態(tài)を考慮して dp[i][j] を最小値で更新します。








  
  
  複雑




時(shí)間計(jì)算量: O(n * m * L) ここで、n はロボットの數(shù)、m は工場(chǎng)の數(shù)、L は工場(chǎng)が処理できる修理の上限です。

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


このソリューションは、工場(chǎng)出荷時(shí)の制限內(nèi)で修理されるすべてのロボットの最小移動(dòng)距離を効率的に計(jì)算します。

連絡(luò)先リンク

このシリーズが役立つと思われた場(chǎng)合は、GitHub で リポジトリ にスターを付けるか、お?dú)荬巳毪辘违僵`シャル ネットワークで投稿を共有することを検討してください。あなたのサポートは私にとって大きな意味を持ちます!

このような役立つコンテンツがさらに必要な場(chǎng)合は、お?dú)葺Xにフォローしてください:


LinkedIn
GitHub



          

            
  

            
        
以上が最小総移動(dòng)距離の詳細(xì)內(nèi)容です。詳細(xì)については、PHP 中國(guó)語(yǔ) Web サイトの他の関連記事を參照してください。