Jumlah Jarak Perjalanan Minimum

2463. Jumlah Jarak Perjalanan Minimum

Kesukaran: Sukar

Topik: Tatasusunan, Pengaturcaraan Dinamik, Isih

Terdapat beberapa robot dan kilang pada paksi X. Anda diberikan robot tatasusunan integer di mana robot[i] ialah kedudukan robot i^th. Anda juga diberikan kilang tatasusunan integer 2D di mana kilang[j] = [kedudukan_j, had_j] menunjukkan bahawa kedudukan_j ialah kedudukan j _ke kilang dan kilang j_ke boleh membaiki paling banyak had_j robot.

Kedudukan setiap robot adalah unik. Kedudukan setiap kilang juga unik. Ambil perhatian bahawa robot boleh dalam kedudukan yang sama sebagai kilang pada mulanya.

Semua robot pada mulanya rosak; mereka terus bergerak ke satu arah. Arahnya boleh menjadi arah negatif atau positif paksi-X. Apabila robot sampai ke kilang yang tidak mencapai hadnya, kilang itu membaiki robot itu dan ia berhenti bergerak.

Pada bila-bila masa, anda boleh menetapkan arah awal untuk bergerak untuk beberapa robot. Sasaran anda adalah untuk meminimumkan jumlah jarak yang dilalui oleh semua robot.

Pulangan jumlah jarak minimum yang dilalui oleh semua robot. Kes ujian dijana supaya semua robot boleh dibaiki.

Perhatikan bahawa

• Semua robot bergerak pada kelajuan yang sama.
• Jika dua robot bergerak ke arah yang sama, mereka tidak akan berlanggar.
• Jika dua robot bergerak ke arah bertentangan dan mereka bertemu pada satu ketika, mereka tidak berlanggar. Mereka bersilang antara satu sama lain.
• Jika robot melalui kilang yang mencapai hadnya, ia melintasinya seolah-olah ia tidak wujud.
• Jika robot bergerak dari kedudukan x ke kedudukan y, jarak yang digerakkan ialah |y - x|.

Contoh 1:

• Input: robot = [0,4,6], kilang = [[2,2],[6,2]]
• Output: 4
• Penjelasan: Seperti yang ditunjukkan dalam rajah:
  • Robot pertama pada kedudukan 0 bergerak ke arah positif. Ia akan dibaiki di kilang pertama.
  • Robot kedua pada kedudukan 4 bergerak ke arah negatif. Ia akan dibaiki di kilang pertama.
  • Robot ketiga di kedudukan 6 akan dibaiki di kilang kedua. Ia tidak perlu bergerak.
  • Had kilang pertama ialah 2, dan ia menetapkan 2 robot.
  • Had kilang kedua ialah 2, dan ia menetapkan 1 robot.
  • Jumlah jarak ialah |2 - 0| |2 - 4| |6 - 6| = 4. Ia boleh ditunjukkan bahawa kita tidak boleh mencapai jumlah jarak yang lebih baik daripada 4.

Contoh 2:

• Input: robot = [1,-1], kilang = [[-2,1],[2,1]]
• Output: 2
• Penjelasan: Seperti yang ditunjukkan dalam rajah:
  • Robot pertama pada kedudukan 1 bergerak ke arah positif. Ia akan dibaiki di kilang kedua.
  • Robot kedua pada kedudukan -1 bergerak ke arah negatif. Ia akan dibaiki di kilang pertama.
  • Had kilang pertama ialah 1, dan ia menetapkan 1 robot.
  • Had kilang kedua ialah 1, dan ia menetapkan 1 robot.
  • Jumlah jarak ialah |2 - 1| |(-2) - (-1)| = 2. Ia boleh ditunjukkan bahawa kita tidak boleh mencapai jumlah jarak yang lebih baik daripada 2.

Kekangan:

• 1
• kilang[j].panjang == 2
• -10⁹ 9
• 0 j
• Input akan dijana supaya sentiasa boleh membaiki setiap robot.

Petunjuk:

1. Isih robot dan kilang mengikut kedudukan mereka.
2. Selepas mengisih, perhatikan bahawa setiap kilang harus membaiki beberapa subsegmen robot.
3. Cari jumlah jarak minimum untuk membaiki robot pertama dengan kilang j pertama.

Penyelesaian:

Kita boleh menggunakan pengaturcaraan dinamik dengan susunan robot dan kilang yang diisih. Ideanya adalah untuk meminimumkan jarak yang perlu dilalui oleh setiap robot untuk dibaiki oleh kilang, dengan menghormati kapasiti pembaikan setiap kilang. Berikut ialah pecahan langkah demi langkah pendekatan:

1. Isih robot dan tatasusunan kilang mengikut kedudukan. Isih membantu dalam meminimumkan jarak perjalanan kerana kami boleh menetapkan robot berdekatan ke kilang berdekatan.

2. Pendekatan Pengaturcaraan Dinamik: Kami mentakrifkan dp jadual DP 2D[i][j] di mana:

   • saya mewakili robot i pertama.
   • j mewakili kilang j pertama.
   • dp[i][j] menyimpan jumlah jarak minimum untuk membaiki robot i ini menggunakan kilang j ini.

3. Peralihan Negeri:

   • Untuk setiap kilang, cuba baiki subset robot berturut-turut dalam hadnya.
   • Untuk kilang j pada kedudukan p, hitung jarak minimum yang diperlukan untuk memberikan k robot kepadanya dengan menjumlahkan jarak dari setiap robot ke kedudukan kilang.
   • Kemas kini keadaan DP dengan memilih minimum antara membaiki lebih sedikit robot atau menggunakan kapasiti kilang sepenuhnya.

Mari laksanakan penyelesaian ini dalam PHP: 2463. Jumlah Jarak Perjalanan Minimum

<?php /**
 * @param Integer[] $robot
 * @param Integer[][] $factory
 * @return Integer
 */
function minimumTotalDistance($robot, $factory) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
$robot = [0, 4, 6];
$factory = [[2, 2], [6, 2]];
echo minimumTotalDistance($robot, $factory);  // Output: 4

$robot = [1, -1];
$factory = [[-2, 1], [2, 1]];
echo minimumTotalDistance($robot, $factory);  // Output: 2
?>

Penjelasan:

• Isih: Kami mengisih robot dan kilang mengikut kedudukan untuk memastikan kami menugaskan robot berdekatan ke kilang berdekatan.
• Permulaan DP: Mulakan dp[0][0] = 0 kerana tiada robot yang dibaiki oleh tiada kilang bermakna jarak sifar.
• Peralihan Pengaturcaraan Dinamik:
  • Untuk setiap kilang j, kami cuba membaiki robot k yang mendahuluinya dalam hadnya.
  • Jumlah jarak terkumpul dalam sumDist.
  • Kami mengemas kini dp[i][j] dengan nilai minimum selepas membaiki k robot, mengambil kira jarak dan keadaan sebelumnya.

Kerumitan

• Kerumitan Masa: O(n * m * L) dengan n ialah bilangan robot, m ialah bilangan kilang dan L ialah had maksimum pembaikan yang boleh dikendalikan oleh mana-mana kilang.
• Kerumitan Ruang: O(n * m) untuk jadual DP.

Penyelesaian ini dengan cekap mengira jarak perjalanan minimum untuk semua robot untuk dibaiki dalam had kilang mereka.

Pautan Kenalan

Jika anda mendapati siri ini membantu, sila pertimbangkan untuk memberi repositori bintang di GitHub atau berkongsi siaran pada rangkaian sosial kegemaran anda ?. Sokongan anda amat bermakna bagi saya!

Jika anda mahukan kandungan yang lebih berguna seperti ini, sila ikuti saya:

• LinkedIn
• GitHub

Atas ialah kandungan terperinci Jumlah Jarak Perjalanan Minimum. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!