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!

Artikel Panas

<🎜>: Bubble Gum Simulator Infinity - Cara Mendapatkan dan Menggunakan Kekunci Diraja
4 minggu yang lalu By 尊渡假赌尊渡假赌尊渡假赌
Nordhold: Sistem Fusion, dijelaskan
4 minggu yang lalu By 尊渡假赌尊渡假赌尊渡假赌
Mandragora: Whispers of the Witch Tree - Cara Membuka Kunci Cangkuk Bergelut
3 minggu yang lalu By 尊渡假赌尊渡假赌尊渡假赌

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)

Topik panas

Tutorial Java
1672
14
Tutorial PHP
1276
29
Tutorial C#
1256
24
Terangkan hashing kata laluan yang selamat di PHP (mis., Password_hash, password_verify). Mengapa tidak menggunakan MD5 atau SHA1? Terangkan hashing kata laluan yang selamat di PHP (mis., Password_hash, password_verify). Mengapa tidak menggunakan MD5 atau SHA1? Apr 17, 2025 am 12:06 AM

Dalam php, kata laluan_hash dan kata laluan 1) password_hash menjana hash yang mengandungi nilai garam untuk meningkatkan keselamatan. 2) Kata Laluan_verify Sahkan kata laluan dan pastikan keselamatan dengan membandingkan nilai hash. 3) MD5 dan SHA1 terdedah dan kekurangan nilai garam, dan tidak sesuai untuk keselamatan kata laluan moden.

Bagaimanakah jenis membayangkan jenis PHP, termasuk jenis skalar, jenis pulangan, jenis kesatuan, dan jenis yang boleh dibatalkan? Bagaimanakah jenis membayangkan jenis PHP, termasuk jenis skalar, jenis pulangan, jenis kesatuan, dan jenis yang boleh dibatalkan? Apr 17, 2025 am 12:25 AM

Jenis PHP meminta untuk meningkatkan kualiti kod dan kebolehbacaan. 1) Petua Jenis Skalar: Oleh kerana Php7.0, jenis data asas dibenarkan untuk ditentukan dalam parameter fungsi, seperti INT, Float, dan lain -lain. 2) Return Type Prompt: Pastikan konsistensi jenis nilai pulangan fungsi. 3) Jenis Kesatuan Prompt: Oleh kerana Php8.0, pelbagai jenis dibenarkan untuk ditentukan dalam parameter fungsi atau nilai pulangan. 4) Prompt jenis yang boleh dibatalkan: membolehkan untuk memasukkan nilai null dan mengendalikan fungsi yang boleh mengembalikan nilai null.

PHP dan Python: Paradigma yang berbeza dijelaskan PHP dan Python: Paradigma yang berbeza dijelaskan Apr 18, 2025 am 12:26 AM

PHP terutamanya pengaturcaraan prosedur, tetapi juga menyokong pengaturcaraan berorientasikan objek (OOP); Python menyokong pelbagai paradigma, termasuk pengaturcaraan OOP, fungsional dan prosedur. PHP sesuai untuk pembangunan web, dan Python sesuai untuk pelbagai aplikasi seperti analisis data dan pembelajaran mesin.

PHP dan Python: Contoh dan perbandingan kod PHP dan Python: Contoh dan perbandingan kod Apr 15, 2025 am 12:07 AM

PHP dan Python mempunyai kelebihan dan kekurangan mereka sendiri, dan pilihannya bergantung kepada keperluan projek dan keutamaan peribadi. 1.PHP sesuai untuk pembangunan pesat dan penyelenggaraan aplikasi web berskala besar. 2. Python menguasai bidang sains data dan pembelajaran mesin.

Bagaimana anda menghalang suntikan SQL di PHP? (Penyataan yang disediakan, PDO) Bagaimana anda menghalang suntikan SQL di PHP? (Penyataan yang disediakan, PDO) Apr 15, 2025 am 12:15 AM

Menggunakan penyataan preprocessing dan PDO dalam PHP secara berkesan dapat mencegah serangan suntikan SQL. 1) Gunakan PDO untuk menyambung ke pangkalan data dan tetapkan mod ralat. 2) Buat kenyataan pra -proses melalui kaedah menyediakan dan lulus data menggunakan ruang letak dan laksanakan kaedah. 3) Hasil pertanyaan proses dan pastikan keselamatan dan prestasi kod.

PHP: Pengendalian pangkalan data dan logik sisi pelayan PHP: Pengendalian pangkalan data dan logik sisi pelayan Apr 15, 2025 am 12:15 AM

PHP menggunakan sambungan MySQLI dan PDO untuk berinteraksi dalam operasi pangkalan data dan pemprosesan logik sisi pelayan, dan memproses logik sisi pelayan melalui fungsi seperti pengurusan sesi. 1) Gunakan MySQLI atau PDO untuk menyambung ke pangkalan data dan laksanakan pertanyaan SQL. 2) Mengendalikan permintaan HTTP dan status pengguna melalui pengurusan sesi dan fungsi lain. 3) Gunakan urus niaga untuk memastikan atomik operasi pangkalan data. 4) Mencegah suntikan SQL, gunakan pengendalian pengecualian dan sambungan penutup untuk debugging. 5) Mengoptimumkan prestasi melalui pengindeksan dan cache, tulis kod yang sangat mudah dibaca dan lakukan pengendalian ralat.

Tujuan PHP: Membina Laman Web Dinamik Tujuan PHP: Membina Laman Web Dinamik Apr 15, 2025 am 12:18 AM

PHP digunakan untuk membina laman web dinamik, dan fungsi terasnya termasuk: 1. Menjana kandungan dinamik dan menghasilkan laman web secara real time dengan menyambung dengan pangkalan data; 2. Proses Interaksi Pengguna dan Penyerahan Bentuk, Sahkan Input dan Menanggapi Operasi; 3. Menguruskan sesi dan pengesahan pengguna untuk memberikan pengalaman yang diperibadikan; 4. Mengoptimumkan prestasi dan ikuti amalan terbaik untuk meningkatkan kecekapan dan keselamatan laman web.

Memilih antara php dan python: panduan Memilih antara php dan python: panduan Apr 18, 2025 am 12:24 AM

PHP sesuai untuk pembangunan web dan prototaip pesat, dan Python sesuai untuk sains data dan pembelajaran mesin. 1.Php digunakan untuk pembangunan web dinamik, dengan sintaks mudah dan sesuai untuk pembangunan pesat. 2. Python mempunyai sintaks ringkas, sesuai untuk pelbagai bidang, dan mempunyai ekosistem perpustakaan yang kuat.

See all articles