Rumah pembangunan bahagian belakang tutorial php Jumlah Jarak Perjalanan Minimum

Jumlah Jarak Perjalanan Minimum

Nov 03, 2024 am 03:45 AM

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 ith. Anda juga diberikan kilang tatasusunan integer 2D di mana kilang[j] = [kedudukanj, hadj] menunjukkan bahawa kedudukanj ialah kedudukan j ke kilang dan kilang jke boleh membaiki paling banyak hadj 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:

Minimum Total Distance Traveled

  • 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:

Minimum Total Distance Traveled

  • 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 <= robot.length, factory.length <= 100
  • kilang[j].panjang == 2
  • -109 <= robot[i], kedudukanj <= 109
  • 0 <= hadj <= robot.length
  • 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






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!

Kenyataan Laman Web ini
Kandungan artikel ini disumbangkan secara sukarela oleh netizen, dan hak cipta adalah milik pengarang asal. Laman web ini tidak memikul tanggungjawab undang-undang yang sepadan. Jika anda menemui sebarang kandungan yang disyaki plagiarisme atau pelanggaran, sila hubungi admin@php.cn

Alat AI Hot

Undresser.AI Undress

Undresser.AI Undress

Apl berkuasa AI untuk mencipta foto bogel yang realistik

AI Clothes Remover

AI Clothes Remover

Alat AI dalam talian untuk mengeluarkan pakaian daripada foto.

Undress AI Tool

Undress AI Tool

Gambar buka pakaian secara percuma

Clothoff.io

Clothoff.io

Penyingkiran pakaian AI

Video Face Swap

Video Face Swap

Tukar muka dalam mana-mana video dengan mudah menggunakan alat tukar muka AI percuma kami!

Alat panas

Notepad++7.3.1

Notepad++7.3.1

Editor kod yang mudah digunakan dan percuma

SublimeText3 versi Cina

SublimeText3 versi Cina

Versi Cina, sangat mudah digunakan

Hantar Studio 13.0.1

Hantar Studio 13.0.1

Persekitaran pembangunan bersepadu PHP yang berkuasa

Dreamweaver CS6

Dreamweaver CS6

Alat pembangunan web visual

SublimeText3 versi Mac

SublimeText3 versi Mac

Perisian penyuntingan kod peringkat Tuhan (SublimeText3)

Jelaskan JSON Web Tokens (JWT) dan kes penggunaannya dalam PHP API. Jelaskan JSON Web Tokens (JWT) dan kes penggunaannya dalam PHP API. Apr 05, 2025 am 12:04 AM

JWT adalah standard terbuka berdasarkan JSON, yang digunakan untuk menghantar maklumat secara selamat antara pihak, terutamanya untuk pengesahan identiti dan pertukaran maklumat. 1. JWT terdiri daripada tiga bahagian: header, muatan dan tandatangan. 2. Prinsip kerja JWT termasuk tiga langkah: menjana JWT, mengesahkan JWT dan muatan parsing. 3. Apabila menggunakan JWT untuk pengesahan di PHP, JWT boleh dijana dan disahkan, dan peranan pengguna dan maklumat kebenaran boleh dimasukkan dalam penggunaan lanjutan. 4. Kesilapan umum termasuk kegagalan pengesahan tandatangan, tamat tempoh, dan muatan besar. Kemahiran penyahpepijatan termasuk menggunakan alat debugging dan pembalakan. 5. Pengoptimuman prestasi dan amalan terbaik termasuk menggunakan algoritma tandatangan yang sesuai, menetapkan tempoh kesahihan dengan munasabah,

Apakah penghitungan (enums) dalam Php 8.1? Apakah penghitungan (enums) dalam Php 8.1? Apr 03, 2025 am 12:05 AM

Fungsi penghitungan dalam Php8.1 meningkatkan kejelasan dan jenis keselamatan kod dengan menentukan pemalar yang dinamakan. 1) Penghitungan boleh menjadi bilangan bulat, rentetan atau objek, meningkatkan kebolehbacaan kod dan keselamatan jenis. 2) Penghitungan adalah berdasarkan kelas dan menyokong ciri-ciri berorientasikan objek seperti traversal dan refleksi. 3) Penghitungan boleh digunakan untuk perbandingan dan tugasan untuk memastikan keselamatan jenis. 4) Penghitungan menyokong penambahan kaedah untuk melaksanakan logik kompleks. 5) Pemeriksaan jenis dan pengendalian ralat yang ketat boleh mengelakkan kesilapan biasa. 6) Penghitungan mengurangkan nilai sihir dan meningkatkan keupayaan, tetapi memberi perhatian kepada pengoptimuman prestasi.

Bagaimanakah sesi merampas kerja dan bagaimana anda dapat mengurangkannya dalam PHP? Bagaimanakah sesi merampas kerja dan bagaimana anda dapat mengurangkannya dalam PHP? Apr 06, 2025 am 12:02 AM

Sesi rampasan boleh dicapai melalui langkah -langkah berikut: 1. Dapatkan ID Sesi, 2. Gunakan ID Sesi, 3. Simpan sesi aktif. Kaedah untuk mengelakkan rampasan sesi dalam PHP termasuk: 1. Gunakan fungsi Sesi_Regenerate_ID () untuk menjana semula ID Sesi, 2. Data sesi stor melalui pangkalan data, 3.

Huraikan prinsip -prinsip yang kukuh dan bagaimana ia memohon kepada pembangunan PHP. Huraikan prinsip -prinsip yang kukuh dan bagaimana ia memohon kepada pembangunan PHP. Apr 03, 2025 am 12:04 AM

Penerapan prinsip pepejal dalam pembangunan PHP termasuk: 1. Prinsip Tanggungjawab Tunggal (SRP): Setiap kelas bertanggungjawab untuk hanya satu fungsi. 2. Prinsip Terbuka dan Tutup (OCP): Perubahan dicapai melalui lanjutan dan bukannya pengubahsuaian. 3. Prinsip Penggantian Lisch (LSP): Subkelas boleh menggantikan kelas asas tanpa menjejaskan ketepatan program. 4. Prinsip Pengasingan Antara Muka (ISP): Gunakan antara muka halus untuk mengelakkan kebergantungan dan kaedah yang tidak digunakan. 5. Prinsip Inversi Ketergantungan (DIP): Modul peringkat tinggi dan rendah bergantung kepada abstraksi dan dilaksanakan melalui suntikan ketergantungan.

Terangkan pengikatan statik lewat dalam php (statik: :). Terangkan pengikatan statik lewat dalam php (statik: :). Apr 03, 2025 am 12:04 AM

Mengikat statik (statik: :) Melaksanakan pengikatan statik lewat (LSB) dalam PHP, yang membolehkan kelas panggilan dirujuk dalam konteks statik dan bukannya menentukan kelas. 1) Proses parsing dilakukan pada masa runtime, 2) Cari kelas panggilan dalam hubungan warisan, 3) ia boleh membawa overhead prestasi.

Apakah Prinsip Reka Bentuk API REST? Apakah Prinsip Reka Bentuk API REST? Apr 04, 2025 am 12:01 AM

Prinsip reka bentuk Restapi termasuk definisi sumber, reka bentuk URI, penggunaan kaedah HTTP, penggunaan kod status, kawalan versi, dan benci. 1. Sumber harus diwakili oleh kata nama dan dikekalkan pada hierarki. 2. Kaedah HTTP harus mematuhi semantik mereka, seperti GET digunakan untuk mendapatkan sumber. 3. Kod status hendaklah digunakan dengan betul, seperti 404 bermakna sumber tidak wujud. 4. Kawalan versi boleh dilaksanakan melalui URI atau header. 5. Boots Operasi Pelanggan Hateoas melalui pautan sebagai tindak balas.

Bagaimanakah anda mengendalikan pengecualian dengan berkesan dalam PHP (cuba, menangkap, akhirnya, membuang)? Bagaimanakah anda mengendalikan pengecualian dengan berkesan dalam PHP (cuba, menangkap, akhirnya, membuang)? Apr 05, 2025 am 12:03 AM

Dalam PHP, pengendalian pengecualian dicapai melalui percubaan, menangkap, akhirnya, dan membuang kata kunci. 1) blok percubaan mengelilingi kod yang boleh membuang pengecualian; 2) Blok tangkapan mengendalikan pengecualian; 3) Akhirnya Blok memastikan bahawa kod itu sentiasa dilaksanakan; 4) Lemparan digunakan untuk membuang pengecualian secara manual. Mekanisme ini membantu meningkatkan keteguhan dan mengekalkan kod anda.

Apakah kelas tanpa nama di PHP dan kapan anda boleh menggunakannya? Apakah kelas tanpa nama di PHP dan kapan anda boleh menggunakannya? Apr 04, 2025 am 12:02 AM

Fungsi utama kelas tanpa nama dalam PHP adalah untuk membuat objek satu kali. 1. Kelas tanpa nama membenarkan kelas tanpa nama ditakrifkan secara langsung dalam kod, yang sesuai untuk keperluan sementara. 2. Mereka boleh mewarisi kelas atau melaksanakan antara muka untuk meningkatkan fleksibiliti. 3. Beri perhatian kepada prestasi dan kebolehbacaan kod apabila menggunakannya, dan elakkan berulang kali menentukan kelas tanpa nama yang sama.

See all articles