Ambil Hadiah Daripada Longgokan Terkaya

2558. Ambil Hadiah Daripada Longgokan Terkaya

Kesukaran: Mudah

Topik: Tatasusunan, Timbunan (Baris Gilir Keutamaan), Simulasi

Anda diberi hadiah tatasusunan integer yang menandakan bilangan hadiah dalam pelbagai longgokan. Setiap saat, anda melakukan perkara berikut:

• Pilih longgokan dengan bilangan maksimum hadiah.
• Jika terdapat lebih daripada satu longgokan dengan bilangan maksimum hadiah, pilih mana-mana.
• Tinggalkan di belakang lantai punca kuasa dua bilangan hadiah dalam longgokan. Ambil selebihnya hadiah.

Kembalikan bilangan hadiah yang tinggal selepas k saat.

Contoh 1:

• Input: hadiah = [25,64,9,4,100], k = 4
• Output: 29
• Penjelasan: Hadiah diambil dengan cara berikut:
  • Dalam detik pertama, longgokan terakhir dipilih dan 10 hadiah ditinggalkan.
  • Kemudian longgokan kedua dipilih dan 8 hadiah ditinggalkan.
  • Selepas itu longgokan pertama dipilih dan 5 hadiah ditinggalkan.
  • Akhirnya, longgokan terakhir dipilih semula dan 3 hadiah ditinggalkan.
  • Hadiah terakhir yang tinggal ialah [5,8,9,4,3], jadi jumlah bilangan hadiah yang tinggal ialah 29.

Contoh 2:

• Input: hadiah = [1,1,1,1], k = 4
• Output: 4
• Penjelasan: Dalam kes ini, tidak kira longgokan mana yang anda pilih, anda perlu meninggalkan 1 hadiah dalam setiap longgokan.
  • Iaitu, anda tidak boleh membawa sebarang longgokan bersama anda.
  • Jadi, jumlah hadiah yang tinggal ialah 4.

Kekangan:

• 1 <= hadiah.panjang <= 10³
• 1 <= hadiah[i] <= 10⁹
• 1 <= k <= 10³

Petunjuk:

1. Bagaimana anda boleh menjejaki hadiah terbesar dalam tatasusunan
2. Apakah cara yang cekap untuk mencari punca kuasa dua nombor?
3. Bolehkah anda terus menambah nilai hadiah sambil memastikan ia berada dalam susunan tertentu?
4. Bolehkah kita menggunakan baris gilir keutamaan atau timbunan di sini?

Penyelesaian:

Kami boleh menggunakan timbunan maksimum (baris gilir keutamaan) kerana kami perlu berulang kali memilih longgokan dengan bilangan maksimum hadiah. Timbunan maksimum akan membolehkan kami mengakses longgokan terbesar dengan cekap dalam masa yang tetap dan mengemas kini longgokan selepas mengambil hadiah daripada longgokan.

Pendekatan:

1. Gunakan Max-Heap:

   • Memandangkan kita perlu berulang kali mendapatkan longgokan dengan bilangan maksimum hadiah, timbunan maksimum (baris gilir keutamaan) adalah ideal. Dalam PHP, kita boleh menggunakan SplPriorityQueue, iaitu baris gilir keutamaan yang secara lalai berfungsi sebagai timbunan maksimum.
   • Untuk mensimulasikan timbunan maks, kami akan memasukkan bilangan hadiah sebagai nilai negatif, kerana SplPriorityQueue ialah timbunan min secara lalai. Dengan memasukkan nilai negatif, nilai negatif terkecil akan mewakili nombor asal terbesar.

2. Proses Setiap Detik:

   • Dalam setiap saat, letakkan longgokan dengan bilangan maksimum hadiah daripada longgokan.
   • Ambil semua hadiah kecuali lantai punca kuasa dua bilangan hadiah dalam longgokan itu.
   • Tolak longgokan yang diubah suai kembali ke dalam longgokan.

3. Penamatan:

   • Kami berhenti selepas k saat atau setelah kami memproses semua saat.

Mari laksanakan penyelesaian ini dalam PHP: 2558. Ambil Hadiah Daripada Longgokan Terkaya

<?php
/**
 * @param Integer[] $gifts
 * @param Integer $k
 * @return Integer
 */
function pickGifts($gifts, $k) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$gifts1 = [25, 64, 9, 4, 100];
$k1 = 4;
echo pickGifts($gifts1, $k1) . "\n"; // Output: 29

$gifts2 = [1, 1, 1, 1];
$k2 = 4;
echo pickGifts($gifts2, $k2) . "\n"; // Output: 4
?>




<h3>
  
  
  Penjelasan:
</h3>

<ol>
<li>
<p><strong>Permulaan Timbunan</strong>:</p>

<ul>
<li>
SplPriorityQueue digunakan untuk mensimulasikan timbunan maks. Kaedah sisipan membolehkan kami menolak elemen ke dalam timbunan dengan keutamaan.</li>
</ul>
</li>
<li>
<p><strong>Memproses Longgokan Terbesar</strong>:</p>

<ul>
<li>Untuk lelaran k, longgokan terbesar diekstrak menggunakan ekstrak.</li>
<li>Bilangan hadiah yang ditinggalkan dikira sebagai lantai punca kuasa dua cerucuk terbesar semasa menggunakan lantai(sqrt(...)).</li>
<li>Cucuk yang dikurangkan dimasukkan semula ke dalam timbunan.</li>
</ul>
</li>
<li>
<p><strong>Menjumlahkan Baki Hadiah</strong>:</p>

<ul>
<li>Selepas operasi k, semua elemen dalam timbunan diekstrak dan disimpulkan untuk mendapatkan jumlah bilangan hadiah yang tinggal.</li>
</ul>
</li>
<li>
<p><strong>Kes Tepi</strong>:</p>

<ul>
<li>Jika hadiah kosong, hasilnya ialah 0.</li>
<li>Jika k lebih besar daripada bilangan operasi yang mungkin, algoritma mengendalikannya dengan anggun.</li>
</ul>
</li>
</ol>

<h3>
  
  
  Kerumitan Masa:
</h3>

<ul>
<li>
<strong>Operasi timbunan (masukkan dan ekstrak)</strong>: Setiap operasi timbunan (sisipan dan pengekstrakan) mengambil masa <em><strong>O(log n)</strong></em>, di mana <em><strong>n</strong></em> ialah bilangan cerucuk.</li>
<li>
<strong>Loosing melalui k operasi</strong>: Kami melaksanakan <em><strong>k</strong></em> operasi, setiap satunya melibatkan pengekstrakan timbunan dan sisipan, kedua-duanya mengambil <em><strong>O(log n)</strong></em>.</li>
</ul>

<p>Oleh itu, jumlah kerumitan masa ialah <em><strong>O(k log n)</strong></em>, dengan <em><strong>n</strong></em> ialah bilangan cerucuk dan <em><strong>k</strong></em> ialah bilangan saat.</p>

<h3>
  
  
  Contoh Panduan:
</h3>

<p>Untuk input:<br>
</p>
<pre class="brush:php;toolbar:false"><?php
/**
 * @param Integer[] $gifts
 * @param Integer $k
 * @return Integer
 */
function pickGifts($gifts, $k) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$gifts1 = [25, 64, 9, 4, 100];
$k1 = 4;
echo pickGifts($gifts1, $k1) . "\n"; // Output: 29

$gifts2 = [1, 1, 1, 1];
$k2 = 4;
echo pickGifts($gifts2, $k2) . "\n"; // Output: 4
?>

1. Pada mulanya, baris gilir keutamaan mempunyai timbunan: [25, 64, 9, 4, 100].
2. Selepas 1 saat: Pilih 100, tinggalkan 10. Hadiah yang tinggal ialah: [25, 64, 9, 4, 10].
3. Selepas 2 saat: Pilih 64, tinggalkan 8. Hadiah yang selebihnya ialah: [25, 8, 9, 4, 10].
4. Selepas 3 saat: Pilih 25, tinggalkan 5. Hadiah yang tinggal ialah: [5, 8, 9, 4, 10].
5. Selepas 4 saat: Pilih 10, tinggalkan 3. Hadiah yang tinggal ialah: [5, 8, 9, 4, 3].

Jumlah hadiah yang tinggal ialah 5 8 9 4 3 = 29.

Pendekatan ini menyelesaikan masalah dengan cekap menggunakan timbunan maksimum dan berfungsi dengan baik dalam kekangan yang diberikan.

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 Ambil Hadiah Daripada Longgokan Terkaya. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!