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!