Maksimum Produk yang Diminimumkan Diedarkan ke Mana-mana Kedai

2064. Maksimum Minimum Produk yang Diedarkan ke Mana-mana Kedai

Kesukaran: Sederhana

Topik: Tatasusunan, Carian Binari

Anda diberi integer n menunjukkan terdapat n kedai runcit khusus. Terdapat m jenis produk dengan jumlah yang berbeza-beza, yang diberikan sebagai kuantiti tatasusunan integer 0-diindeks, dengan kuantiti[i] mewakili bilangan produk jenis produk i^th.

Anda perlu mengedarkan semua produk ke kedai runcit mengikut peraturan ini:

• Sebuah kedai hanya boleh diberikan paling banyak satu jenis produk tetapi boleh diberikan sebarang jumlah.
• Selepas pengedaran, setiap kedai akan diberikan beberapa bilangan produk (mungkin 0). Biarkan x mewakili bilangan maksimum produk yang diberikan kepada mana-mana kedai. Anda mahu x menjadi sekecil mungkin, iaitu, anda ingin meminimumkan bilangan maksimum produk yang diberikan kepada mana-mana kedai.

Pulangan seminimum mungkin x.

Contoh 1:

• Input: n = 6, kuantiti = [11,6]
• Output: 3
• Penjelasan: Satu cara yang optimum ialah:
  • 11 produk jenis 0 diedarkan kepada empat kedai pertama dalam jumlah ini: 2, 3, 3, 3
  • 6 produk jenis 1 diedarkan ke dua kedai lain dalam jumlah ini: 3, 3
  • Bilangan maksimum produk yang diberikan kepada mana-mana kedai ialah maks(2, 3, 3, 3, 3, 3) = 3.

Contoh 2:

• Input: n = 7, kuantiti = [15,10,10]
• Output: 5
• Penjelasan: Satu cara yang optimum ialah:
  • 15 produk jenis 0 diedarkan kepada tiga kedai pertama dalam jumlah ini: 5, 5, 5
  • 10 produk jenis 1 diedarkan ke dua kedai seterusnya dalam jumlah ini: 5, 5
  • 10 produk jenis 2 diedarkan ke dua kedai terakhir dalam jumlah ini: 5, 5
  • Bilangan maksimum produk yang diberikan kepada mana-mana kedai ialah maks(5, 5, 5, 5, 5, 5, 5) = 5.

Contoh 3:

• Input: n = 1, kuantiti = [100000]
• Output: 100000
• Penjelasan: Satu-satunya cara yang optimum ialah:
  • 100000 produk jenis 0 diedarkan kepada satu-satunya kedai.
  • Bilangan maksimum produk yang diberikan kepada mana-mana kedai ialah maks(100000) = 100000.

Kekangan:

• m == kuantiti.panjang
• 1 <= m <= n <= 10⁵
• 1 <= kuantiti[i] <= 10⁵

Petunjuk:

1. Terdapat sifat monotonik seperti apabila x lebih kecil daripada beberapa nombor, tidak akan ada cara untuk mengagihkan, dan apabila x tidak lebih kecil daripada nombor itu, akan sentiasa ada cara untuk mengagihkan.
2. Jika anda diberi nombor k, di mana bilangan produk yang diberikan kepada mana-mana kedai tidak melebihi k, bolehkah anda menentukan sama ada semua produk boleh diedarkan?
3. Laksanakan fungsi canDistribute(k), yang mengembalikan benar jika anda boleh mengedarkan semua produk supaya mana-mana kedai tidak akan diberikan lebih daripada k produk, dan mengembalikan palsu jika anda tidak boleh. Gunakan fungsi ini untuk carian binari untuk k terkecil yang mungkin.

Penyelesaian:

Kami boleh menggunakan carian binari pada bilangan maksimum produk yang mungkin diberikan kepada mana-mana kedai (x). Berikut ialah penjelasan langkah demi langkah dan penyelesaian PHP:

Pendekatan

1. Persediaan Carian Binari:

   • Tetapkan sempadan bawah (kiri) sebagai 1 (kerana setiap kedai boleh mendapatkan sekurang-kurangnya 1 produk).
   • Tetapkan sempadan atas (kanan) sebagai kuantiti maksimum dalam tatasusunan kuantiti (dalam kes yang paling teruk, satu kedai mendapat semua produk daripada jenis).
   • Matlamat kami adalah untuk meminimumkan nilai x (produk maksimum diberikan kepada mana-mana kedai).

2. Logik Carian Binari:

   • Untuk setiap titik tengah x, semak sama ada ia boleh mengedarkan semua produk supaya tiada kedai yang mempunyai lebih daripada x produk.
   • Gunakan fungsi pembantu bolehDistribute(x) untuk menentukan kebolehlaksanaan.

3. Semakan Kebolehlaksanaan (boleh Edar):

   • Untuk setiap jenis produk dalam kuantiti, hitung bilangan minimum kedai yang diperlukan untuk mengedarkan jenis produk tersebut tanpa melebihi x produk bagi setiap kedai.
   • Jumlah kedai yang diperlukan untuk semua jenis produk.
   • Jika jumlah stor yang diperlukan adalah kurang daripada atau sama dengan n, pengagihan boleh dilakukan dengan x sebagai beban maksimum bagi setiap kedai; jika tidak, ia tidak boleh dilaksanakan.

4. Pelarasan Carian Binari:

   • Jika canDistribute(x) mengembalikan benar, ini bermakna x ialah penyelesaian yang boleh dilaksanakan, tetapi kami mahu meminimumkan x, jadi laraskan sempadan yang betul.
   • Jika ia mengembalikan palsu, tambahkan sempadan kiri kerana x terlalu kecil.

5. Keputusan:

   • Setelah carian binari selesai, kiri akan memegang x minimum yang mungkin.

Mari laksanakan penyelesaian ini dalam PHP: 2064. Maksimum Minimum Produk yang Diedarkan ke Mana-mana Kedai

  
  
  Penjelasan:




bolehMengedarkan fungsi:


Bagi setiap kuantiti, ia mengira stor minimum yang diperlukan dengan membahagikan kuantiti dengan x (menggunakan siling untuk membulatkan kerana setiap kedai boleh mendapatkan bilangan keseluruhan produk).
Ia mengembalikan palsu jika simpanan terkumpul yang diperlukan melebihi n.



Carian Binari pada x:

Carian binari secara berulang mengurangkan julat untuk x sehingga ia menumpu pada nilai minimum yang boleh dilaksanakan.



Kecekapan:


Penyelesaian ini cekap untuk saiz input yang besar (n dan m sehingga 10^5) kerana carian binari berjalan dalam O(log(kuantiti_maks) * m), yang boleh dilaksanakan dalam kekangan yang diberikan.




Pendekatan ini meminimumkan x, memastikan produk diedarkan sekata mungkin di seluruh kedai.

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 Maksimum Produk yang Diminimumkan Diedarkan ke Mana-mana Kedai. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!