1792. Nisbah Purata Lulus Maksimum

Kesukaran: Sederhana

Topik: Susunan, Tamak, Timbunan (Barisan Keutamaan)

Terdapat sekolah yang mempunyai kelas pelajar dan setiap kelas akan menghadapi peperiksaan akhir. Anda diberikan kelas tatasusunan integer 2D, dengan kelas[i] = [lulus_i, jumlah_i]. Anda tahu sebelum ini bahawa dalam kelas i^th, terdapat jumlah_i jumlah pelajar, tetapi hanya lulus_i bilangan pelajar akan lulus peperiksaan.

Anda juga diberikan pelajar tambahan integer. Terdapat seorang lagi pelajar cemerlang Pelajar tambahan yang dijamin untuk lulus peperiksaan mana-mana kelas yang ditugaskan kepada mereka. Anda ingin menugaskan setiap pelajar tambahan kepada kelas dengan cara memaksimumkan purata nisbah lulus merentas semua kelas.

nisbah lulus kelas adalah sama dengan bilangan pelajar kelas yang akan lulus peperiksaan dibahagikan dengan jumlah bilangan pelajar kelas itu. nisbah lulus purata ialah jumlah nisbah lulus semua kelas dibahagikan dengan bilangan kelas.

Kembalikan maksimum nisbah kelulusan purata yang mungkin selepas menetapkan pelajar tambahan Pelajar. Jawapan dalam masa 10^-5 daripada jawapan sebenar akan diterima.

Contoh 1:

• Input: kelas = [[1,2],[3,5],[2,2]], pelajar tambahan = 2
• Output: 0.78333
• Penjelasan: Anda boleh menugaskan dua pelajar tambahan ke kelas pertama. Nisbah lulus purata akan sama dengan (3/4 3/5 2/2) / 3 = 0.78333.

Contoh 2:

• Input: kelas = [[2,4],[3,9],[4,5],[2,10]], pelajar tambahan = 4
• Output: 4
• Penjelasan: 0.53485

Kekangan:

• 1 <= classes.length <= 10⁵
• kelas[i].panjang == 2
• 1 <= lulus_i <= jumlah_i <= 10⁵
• 1 <= pelajar tambahan <= 10⁵

Petunjuk:

1. Perhatikan berapa banyak perubahan nisbah lulus apabila anda menambahkan pelajar ke kelas. Jika anda terus menambah pelajar, apakah yang berlaku kepada perubahan nisbah lulus? Semakin ramai pelajar yang anda tambahkan pada kelas, semakin kecil perubahan nisbah lulus.
2. Memandangkan perubahan dalam nisbah lulus sentiasa berkurangan dengan lebih ramai pelajar yang anda tambahkan, maka pelajar pertama yang anda tambahkan pada setiap kelas ialah pelajar yang membuat perubahan terbesar dalam nisbah lulus.
3. Oleh kerana nisbah lulus setiap kelas adalah wajaran yang sama, adalah sentiasa optimum untuk meletakkan pelajar dalam kelas yang membuat perubahan terbesar antara semua kelas lain.
4. Simpan timbunan maksimum saiz kelas semasa dan susunkannya mengikut perubahan nisbah lulus. Untuk setiap pelajar tambahan, ambil bahagian atas timbunan, kemas kini saiz kelas dan letakkan semula dalam timbunan.

Penyelesaian:

Kita boleh menggunakan timbunan maksimum (baris gilir keutamaan). Ini kerana kita perlu mencari kelas yang paling mendapat manfaat dengan cekap (memaksimumkan perubahan dalam nisbah lulus) apabila menambah pelajar tambahan.

Pendekatan:

1. Fahami Pengiraan Keuntungan:

   • Apabila menambah seorang pelajar ke kelas, perubahan dalam nisbah lulus boleh dikira sebagai: keuntungan = (lulus 1)/(jumlah 1) - lulus/jumlah
   • Tugasnya adalah untuk memaksimumkan jumlah nisbah lulus merentas semua kelas dengan mengagihkan Pelajar tambahan secara optimum.

2. Gunakan Max-Heap:

   • Untuk setiap kelas, kira keuntungan awal dan masukkannya ke dalam timbunan maksimum bersama dengan butiran kelas.
   • Setiap elemen timbunan ialah tuple: [keuntungan negatif, lulus, jumlah]. (Kami menggunakan keuntungan negatif kerana SplPriorityQueue PHP ialah timbunan min secara lalai.)

3. Agihkan Pelajar Tambahan Secara Berulang:

   • Pop kelas dengan keuntungan maksimum daripada timbunan.
   • Tambahkan seorang pelajar ke kelas itu, kira semula keuntungan dan tolaknya semula ke dalam timbunan.
   • Ulang sehingga semua Pelajar tambahan diedarkan.

4. Kira Purata Akhir:

   • Setelah semua pelajar tambahan ditugaskan, hitung purata nisbah lulus semua kelas.

Mari laksanakan penyelesaian ini dalam PHP: 1792. Nisbah Purata Lulus Maksimum

  
  
  Penjelasan:




Persediaan Timbunan:


Kami menggunakan timbunan maksimum (baris gilir keutamaan) untuk mengutamakan kelas berdasarkan potensi peningkatan dalam nisbah lulus apabila pelajar tambahan ditambah.
Dalam PHP, SplPriorityQueue digunakan untuk timbunan. Lebih tinggi nilai keutamaan, lebih awal kelas diproses.



Mengagihkan Pelajar Tambahan:

Untuk setiap pelajar tambahan, kami mengekstrak kelas dengan potensi peningkatan tertinggi daripada timbunan.
Selepas menambah seorang pelajar ke kelas itu, kami mengira semula potensi peningkatannya dan memasukkannya semula ke dalam timbunan.



Pengiraan Purata Akhir:


Selepas mengagihkan semua pelajar tambahan, kami mengira jumlah nisbah lulus untuk semua kelas dan mengembalikan purata.



Ketepatan:


Pengiraan dilakukan menggunakan aritmetik titik terapung, yang memastikan jawapan tepat hingga 10^-5 seperti yang diperlukan.





  
  
  Kerumitan:




Kerumitan Masa:


Pengambilan sisipan dan pengekstrakan timbunan O(log N), dengan N ialah bilangan kelas.
Untuk Pelajar tambahan lelaran, kerumitannya ialah O(Pelajar tambahan x log N).
Penjumlahan nisbah lulus akhir ialah O(N).







Kerumitan Angkasa:


Timbunan menyimpan elemen N, jadi kerumitan ruang ialah O(N).







Pelaksanaan ini mengagihkan pelajar tambahan dengan cekap dan mengira nisbah purata lulus maksimum.

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 Nisbah Purata Lulus Maksimum. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!