Had Minimum Bola dalam Beg

1760. Had Minimum Bola dalam Beg

Kesukaran: Sederhana

Topik: Tatasusunan, Carian Binari

Anda diberi nombor tatasusunan integer di mana beg i^th mengandungi nums[i] bola. Anda juga diberikan integer maxOperations.

Anda boleh melakukan operasi berikut pada kebanyakan masa maxOperations:

• Ambil mana-mana beg bola dan bahagikannya kepada dua beg baharu dengan bilangan bola positif.
  • Sebagai contoh, beg 5 bola boleh menjadi dua beg baharu 1 dan 4 bola, atau dua beg baharu 2 dan 3 bola.

Penalti anda ialah maksimum bilangan bola dalam beg. Anda mahu meminimumkan penalti anda selepas operasi.

Kembalikan penalti minimum yang mungkin selepas melakukan operasi.

Contoh 1:

• Input: nombor = [9], maxOperations = 2
• Output: 3
• Penjelasan:
  • Bahagikan beg dengan 9 bola kepada dua beg bersaiz 6 dan 3. [9] -> [6,3].
  • Bahagikan beg dengan 6 bola kepada dua beg saiz 3 dan 3. [6,3] -> [3,3,3].
  • Beg dengan bilangan bola terbanyak mempunyai 3 bola, jadi penalti anda ialah 3 dan anda harus mengembalikan 3.

Contoh 2:

• Input: nombor = [2,4,8,2], maxOperations = 4
• Output: 2
• Penjelasan:
  • Bahagikan beg dengan 8 bola kepada dua beg saiz 4 dan 4. [2,4,8,2] -> [2,4,4,4,2].
  • Bahagikan beg dengan 4 bola kepada dua beg saiz 2 dan 2. [2,4,4,4,2] -> [2,2,2,4,4,2].
  • Bahagikan beg dengan 4 bola kepada dua beg saiz 2 dan 2. [2,2,2,4,4,2] -> [2,2,2,2,2,4,2].
  • Bahagikan beg dengan 4 bola kepada dua beg saiz 2 dan 2. [2,2,2,2,2,4,2] -> [2,2,2,2,2,2,2,2].
  • Beg dengan bilangan bola terbanyak mempunyai 2 bola, jadi penalti anda ialah 2, dan anda harus mengembalikan 2.

Kekangan:

• 1 5
• 1 9

Petunjuk:

1. Mari kita tukar soalan jika kita tahu saiz maksimum beg berapakah bilangan minimum beg yang boleh anda buat
2. perhatikan bahawa apabila saiz maksimum bertambah, bilangan beg minimum berkurangan supaya kita boleh mencari saiz maksimum secara binari

Penyelesaian:

Kita boleh menggunakan carian binari untuk mencari penalti minimum yang mungkin. Wawasan utama ialah jika kita boleh menentukan sama ada penalti tertentu boleh dicapai, kita boleh mengecilkan julat carian menggunakan carian binari.

Langkah-langkah untuk Menyelesaikan:

1. Persediaan Carian Binari:

   • Penalti minimum ialah 1 (semua bola dibahagikan kepada beg bola tunggal).
   • Penalti maksimum ialah nombor terbesar dalam tatasusunan nums.

2. Semakan Kebolehlaksanaan:

   • Untuk pertengahan penalti tertentu, semak sama ada mungkin untuk mencapainya dengan paling banyak pemisahan maxOperations.
   • Untuk melakukan ini, bagi setiap saiz beg dalam angka, kira bilangan belahan yang diperlukan untuk menjadikan semua beg mempunyai bola tengah atau kurang. Jika jumlah pecahan melebihi maxOperations, pertengahan penalti tidak boleh dilaksanakan.

3. Lelaran:

   • Gunakan carian binari untuk melaraskan julat [rendah, tinggi] berdasarkan sama ada pertengahan penalti boleh dilaksanakan.

Mari laksanakan penyelesaian ini dalam PHP: 1760. Had Minimum Bola dalam Beg

<?php /**
 * @param Integer[] $nums
 * @param Integer $maxOperations
 * @return Integer
 */
function minimumSize($nums, $maxOperations) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
 * Helper function to check if a penalty is feasible
 *
 * @param $nums
 * @param $maxOperations
 * @param $penalty
 * @return bool
 */
function canAchievePenalty($nums, $maxOperations, $penalty) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example 1
$nums = [9];
$maxOperations = 2;
echo minimumSize($nums, $maxOperations); // Output: 3

// Example 2
$nums = [2, 4, 8, 2];
$maxOperations = 4;
echo minimumSize($nums, $maxOperations); // Output: 2
?>

Penjelasan:

1. Carian Binari:

   • Ruang carian adalah antara 1 dan nombor maksimum dalam tatasusunan nombor.
   • Titik tengah tengah mewakili penalti semasa yang sedang kami uji.

2. Semakan Kebolehlaksanaan (bolehAchievePenalty):

   • Untuk setiap beg, hitung pembahagian yang diperlukan untuk memastikan semua beg mempunyai bola tengah atau kurang:
     • ceil(bola / pertengahan) - 1 memberikan bilangan belahan yang diperlukan.
   • Jika jumlah pecahan melebihi maxOperations, penalti tidak boleh dilaksanakan.

3. Laraskan Ruang Carian:

   • Jika penalti boleh dilaksanakan, kurangkan sempadan atas (tinggi = pertengahan).
   • Jika tidak, naikkan sempadan bawah (rendah = pertengahan 1).

4. Keputusan:

   • Apabila gelung keluar, rendah mengandungi penalti terkecil yang boleh dilaksanakan.

Kerumitan:

• Kerumitan Masa: O(n . log(maks(bilangan)))
  • Carian binari dijalankan dalam O(log(maks(bilangan))), dan semakan kebolehlaksanaan untuk setiap titik tengah mengambil masa O(n).
• Kerumitan Angkasa: O(1), kerana kami hanya menggunakan ruang tambahan yang berterusan.

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 Had Minimum Bola dalam Beg. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!