Taux de réussite moyen maximum

1792. Taux de réussite moyen maximum

Difficulté :Moyen

Sujets :Array, Greedy, Heap (File d'attente prioritaire)

Il y a une école qui a des classes d'élèves et chaque classe aura un examen final. Vous recevez un tableau d'entiers 2D classes, où classes[i] = [pass_i, total_i]. Vous savez d'avance que dans la i^ième classe, il y a au total_i total d'élèves, mais seul le nombre de réussite_i d'élèves réussira l'examen.

Vous recevez également un nombre entier d'extraÉtudiants. Il existe d'autres étudiants brillants qui sont garantis de réussir l'examen de n'importe quelle classe à laquelle ils sont affectés. Vous souhaitez affecter chacun des étudiants extraStudents à une classe de manière à maximiser le taux de réussite moyen dans toutes les classes.

Le taux de réussite d'une classe est égal au nombre d'élèves de la classe qui réussiront l'examen divisé par le nombre total d'élèves de la classe. Le taux de réussite moyen est la somme des taux de réussite de toutes les classes divisée par le nombre de classes.

Renvoyer le taux de réussite moyen maximum possible après avoir attribué les étudiants extraStudents. Les réponses dans les 10^-5 de la réponse réelle seront acceptées.

Exemple 1 :

• Entrée : classes = [[1,2],[3,5],[2,2]], extraStudents = 2
• Sortie : 0,78333
• Explication : Vous pouvez affecter les deux élèves supplémentaires au premier cours. Le taux de réussite moyen sera égal à (3/4 3/5 2/2) / 3 = 0,78333.

Exemple 2 :

• Entrée : classes = [[2,4],[3,9],[4,5],[2,10]], extraStudents = 4
• Sortie : 4
• Explication :0,53485

Contraintes :

• 1 5
• classes[i].length == 2
• 1 i i 5
• 1 5

Indice :

1. Faites attention à l'ampleur avec laquelle le taux de réussite change lorsque vous ajoutez un élève à la classe. Si vous continuez à ajouter des étudiants, qu’arrive-t-il à l’évolution du taux de réussite ? Plus vous ajoutez d’élèves à une classe, plus le changement du taux de réussite est faible.
2. Étant donné que la variation du taux de réussite diminue toujours avec le nombre d'élèves que vous ajoutez, le tout premier élève que vous ajoutez à chaque classe est celui qui apporte le plus grand changement dans le taux de réussite.
3. Étant donné que le taux de réussite de chaque classe est pondéré de manière égale, il est toujours optimal de placer l'élève dans la classe qui apporte le plus grand changement parmi toutes les autres classes.
4. Gardez un maximum de tailles de classe actuelles et classez-les en fonction de l'évolution du taux de réussite. Pour chaque élève supplémentaire, prenez le haut du tas, mettez à jour la taille de la classe et remettez-la dans le tas.

Solution :

Nous pouvons utiliser un max-heap (file d'attente prioritaire). En effet, nous devons trouver efficacement la classe qui en profite le plus (maximise la modification du taux de réussite) lors de l'ajout d'un élève supplémentaire.

Approche:

1. Comprendre le calcul du gain :

   • Lors de l'ajout d'un élève à une classe, la modification du taux de réussite peut être calculée comme suit : gain = (passe 1)/(total 1) - passe/total
   • La tâche est de maximiser la somme des taux de réussite dans toutes les classes en répartissant les étudiants supplémentaires de manière optimale.

2. Utiliser un Max-Heap :

   • Pour chaque classe, calculez le gain initial et insérez-le dans un tas maximum avec les détails de la classe.
   • Chaque élément du tas est un tuple : [gain négatif, réussite, total]. (Nous utilisons un gain négatif car SplPriorityQueue de PHP est un min-heap par défaut.)

3. Distribuer de manière itérative les étudiants supplémentaires :

   • Faites éclater la classe avec le gain maximum du tas.
   • Ajoutez un élève à cette classe, recalculez le gain et remettez-le dans le tas.
   • Répétez jusqu'à ce que tous les étudiants supplémentaires soient distribués.

4. Calculer la moyenne finale :

   • Une fois tous les étudiants supplémentaires affectés, calculez le taux de réussite moyen de toutes les classes.

Implémentons cette solution en PHP : 1792. Taux de réussite moyen maximum

<?php /**
 * @param Integer[][] $classes
 * @param Integer $extraStudents
 * @return Float
 */
function maxAverageRatio($classes, $extraStudents) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
 * Calculate the extra pass ratio when a student is added to the class
 *
 * @param $pass
 * @param $total
 * @return float|int
 */
private function extraPassRatio($pass, $total)
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$classes = [[1, 2], [3, 5], [2, 2]];
$extraStudents = 2;
echo maxAverageRatio($classes, $extraStudents); // Output: 0.78333

$classes = [[2, 4], [3, 9], [4, 5], [2, 10]];
$extraStudents = 4;
echo maxAverageRatio($classes, $extraStudents); // Output: 0.53485
?>

Explication:

1. Configuration du tas :

   • Nous utilisons un tas maximum (file d'attente prioritaire) pour hiérarchiser les classes en fonction de leur amélioration potentielle du taux de réussite lorsqu'un élève supplémentaire est ajouté.
   • En PHP, SplPriorityQueue est utilisé pour le tas. Plus la valeur de priorité est élevée, plus la classe est traitée tôt.

2. Répartition des étudiants supplémentaires :

   • Pour chaque élève supplémentaire, nous extrayons du tas la classe avec le potentiel d'amélioration le plus élevé.
   • Après avoir ajouté un élève à cette classe, nous recalculons son potentiel d'amélioration et le réinsérons dans le tas.

3. Calcul moyen final :

   • Après avoir réparti tous les étudiants supplémentaires, nous calculons le taux de réussite total pour toutes les classes et renvoyons la moyenne.

4. Précision :

   • Les calculs sont effectués à l'aide de l'arithmétique à virgule flottante, ce qui garantit que les réponses sont précises à 10^-5 selon les besoins.

Complexité:

• Complexité temporelle :

  • L'insertion et l'extraction du tas prennent O(log N), où N est le nombre de classes.
  • Pour les itérations extraStudents, la complexité est O (extraStudents x log N).
  • La somme finale du taux de réussite est O(N).

• Complexité spatiale :

  • Le tas stocke N éléments, donc la complexité spatiale est O(N).

Cette implémentation répartit efficacement les étudiants supplémentaires et calcule le taux de réussite moyen maximum.

Liens de contact

Si vous avez trouvé cette série utile, pensez à donner une étoile au référentiel sur GitHub ou à partager la publication sur vos réseaux sociaux préférés ?. Votre soutien signifierait beaucoup pour moi !

Si vous souhaitez du contenu plus utile comme celui-ci, n'hésitez pas à me suivre :

• LinkedIn
• GitHub

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!