Maximale durchschnittliche Erfolgsquote

1792. Maximale durchschnittliche Erfolgsquote

Schwierigkeit:Mittel

Themen:Array, Greedy, Heap (Prioritätswarteschlange)

Es gibt eine Schule mit Schülerklassen und jede Klasse hat eine Abschlussprüfung. Sie erhalten ein 2D-Integer-Array „classes“, wobei „classes[i] = [pass_i, total_i]“ gilt. Sie wissen im Voraus, dass es in der i^tenKlasse insgesamt_i Gesamtschüler gibt, aber nur eine bestandene_i Anzahl von Schülern wird die Prüfung bestehen.

Sie erhalten außerdem eine Ganzzahl extraStudents. Es gibt noch weitere hervorragende Studenten, die garantiert sind, die Prüfung jeder Klasse zu bestehen, der sie zugewiesen sind. Sie möchten jeden der extraStudents-Schüler so einer Klasse zuordnen, dass die durchschnittliche Erfolgsquote über alle Klassen hinweg maximiert

Die Bestehensquote einer Klasse entspricht der Anzahl der Schüler der Klasse, die die Prüfung bestehen, geteilt durch die Gesamtzahl der Schüler der Klasse. Die durchschnittliche Erfolgsquote

Geben Sie die maximal ^{mögliche durchschnittliche Erfolgsquote zurück, nachdem Sie die zusätzlichen Studenten zugewiesen haben. Antworten innerhalb von 10}-5

Beispiel 1:

• Eingabe:
classes = [[1,2],[3,5],[2,2]], extraStudents = 2
• Ausgabe:
0,78333
• Erklärung:
Sie können die beiden zusätzlichen Schüler der ersten Klasse zuordnen. Das durchschnittliche Erfolgsverhältnis beträgt (3/4 3/5 2/2) / 3 = 0,78333.

Beispiel 2:

• Eingabe:
classes = [[2,4],[3,9],[4,5],[2,10]], extraStudents = 4
• Ausgabe:
4
• Erklärung:
0,53485

Einschränkungen:

• ^{1 <= klassen.länge <= 10}5
classes[i].length == 2
• _{1 <= bestanden}i _{<= gesamt}i ^{<= 10}5
• ^{1 <= zusätzlicheStudenten <= 10}5

Hinweis:

1. Achten Sie darauf, wie stark sich die Erfolgsquote ändert, wenn Sie einen Schüler zur Klasse hinzufügen. Was passiert mit der Änderung der Erfolgsquote, wenn Sie weitere Studierende hinzufügen? Je mehr Schüler Sie einer Klasse hinzufügen, desto geringer wird die Veränderung der Erfolgsquote.
2. Da die Veränderung der Erfolgsquote immer kleiner wird, je mehr Schüler Sie hinzufügen, ist der allererste Schüler, den Sie jeder Klasse hinzufügen, derjenige, der die größte Veränderung in der Erfolgsquote bewirkt.
3. Da die Erfolgsquote jeder Klasse gleich gewichtet ist, ist es immer optimal, den Schüler der Klasse zuzuordnen, die im Vergleich zu allen anderen Klassen die größte Veränderung bewirkt.
4. Behalten Sie einen maximalen Haufen der aktuellen Klassengrößen und ordnen Sie sie nach der Änderung der Erfolgsquote. Nehmen Sie für jeden zusätzlichen Schüler den oberen Rand des Heaps, aktualisieren Sie die Klassengröße und legen Sie ihn wieder auf den Heap.

Lösung:

Wir können einen Max-Heap (Prioritätswarteschlange) verwenden. Dies liegt daran, dass wir effizient die Klasse finden müssen, die am meisten davon profitiert (die Änderung der Erfolgsquote maximiert), wenn wir einen zusätzlichen Schüler hinzufügen.

Ansatz:

1. Verstehen Sie die Gewinnberechnung:

   • Beim Hinzufügen eines Schülers zu einer Klasse kann die Änderung der Erfolgsquote wie folgt berechnet werden: Gewinn = (Durchgang 1)/(Gesamt 1) – Durchgang/Gesamt
   • Die Aufgabe besteht darin, die Summe der Erfolgsquoten über alle Klassen hinweg zu maximieren, indem zusätzliche Schüler optimal verteilt werden.

2. Verwenden Sie einen Max-Heap:

   • Berechnen Sie für jede Klasse den anfänglichen Gewinn und fügen Sie ihn zusammen mit den Klassendetails in einen Max-Heap ein.
   • Jedes Heap-Element ist ein Tupel: [negativer Gewinn, bestanden, insgesamt]. (Wir verwenden eine negative Verstärkung, da PHPs SplPriorityQueue standardmäßig ein Min-Heap ist.)

3. Zusätzliche Schüler iterativ verteilen:

   • Öffnen Sie die Klasse mit dem maximalen Gewinn aus dem Heap.
   • Fügen Sie einen Schüler zu dieser Klasse hinzu, berechnen Sie den Gewinn neu und verschieben Sie ihn zurück in den Haufen.
   • Wiederholen, bis alle zusätzlichen Schüler verteilt sind.

4. Berechnen Sie den endgültigen Durchschnitt:

   • Sobald alle zusätzlichen Schüler zugewiesen sind, berechnen Sie die durchschnittliche Erfolgsquote aller Klassen.

Lassen Sie uns diese Lösung in PHP implementieren: 1792. Maximale durchschnittliche Erfolgsquote

  
  
  Erläuterung:




Heap-Setup:


Wir verwenden einen Max-Heap (Prioritätswarteschlange), um Klassen basierend auf ihrer potenziellen Verbesserung der Erfolgsquote zu priorisieren, wenn ein zusätzlicher Schüler hinzugefügt wird.
In PHP wird SplPriorityQueue für den Heap verwendet. Je höher der Prioritätswert, desto früher wird die Klasse verarbeitet.



Zusätzliche Studenten verteilen:

Für jeden zusätzlichen Schüler extrahieren wir die Klasse mit dem höchsten Verbesserungspotenzial aus dem Haufen.
Nachdem wir einen Schüler zu dieser Klasse hinzugefügt haben, berechnen wir dessen potenzielle Verbesserung neu und fügen ihn erneut in den Haufen ein.



Endgültige Durchschnittsberechnung:


Nachdem wir alle zusätzlichen Schüler verteilt haben, berechnen wir die Gesamterfolgsquote für alle Klassen und geben den Durchschnitt zurück.



Präzision:


Die Berechnungen werden mithilfe der Gleitkomma-Arithmetik durchgeführt, wodurch sichergestellt wird, dass die Antworten wie erforderlich auf 10^-5 genau sind.





  
  
  Komplexität:




Zeitkomplexität:


Heap-Einfügung und -Extraktion benötigen O(log N), wobei N die Anzahl der Klassen ist.
Für extraStudents Iterationen beträgt die Komplexität O(extraStudents x log N).
Die endgültige Summe des Passverhältnisses ist O(N).







Weltraumkomplexität:


Der Heap speichert N Elemente, daher beträgt die Raumkomplexität O(N).







Diese Implementierung verteilt die zusätzlichen Studenten effizient und berechnet die maximale durchschnittliche Erfolgsquote.

Kontaktlinks

Wenn Sie diese Serie hilfreich fanden, denken Sie bitte darüber nach, dem Repository einen Stern auf GitHub zu geben oder den Beitrag in Ihren bevorzugten sozialen Netzwerken zu teilen? Ihre Unterstützung würde mir sehr viel bedeuten!

Wenn Sie weitere hilfreiche Inhalte wie diesen wünschen, folgen Sie mir gerne:


LinkedIn
GitHub



          

            
  

            
        

Das obige ist der detaillierte Inhalt vonMaximale durchschnittliche Erfolgsquote. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!