C# LeetCode 1792: Proporción Promedio Máxima de Aprobados

C# LeetCode 1792 Proporción Promedio Máxima de Aprobados Medium

Intuición

El reto consiste en decidir en cada paso a qué clase asignar un estudiante extra para maximizar la proporción promedio de aprobados. La idea clave es medir la ganancia marginal que obtiene cada clase al sumar un estudiante que aprueba y escoger siempre la mayor. Para esto, una estructura de tipo cola de prioridad resulta ideal, pues permite extraer repetidamente la mejor opción con eficiencia O(log n) por operación.

Enfoque

1 Calcular para cada clase su ganancia inicial al añadir un estudiante que aprueba y meterla en una cola de prioridad ordenada por esa ganancia. 2 Repetir extraStudents veces tomar la clase con mayor ganancia, asignarle un estudiante extra y recalcular su nueva ganancia para volver a insertarla. 3 Al finalizar, sumar las proporciones finales de todas las clases y dividir entre el número de clases para obtener la media.

Ejemplo rápido

Clases A 1 de 2 y B 3 de 5. Ganancias iniciales al añadir un alumno que aprueba A 0,1667 y B 0,0667. Primera asignación escoge A pasa a A 2 de 3. Recomputamos A su nueva ganancia es 0,0833, mientras que B mantiene 0,0667, por lo que en la segunda asignación aún gana A pasa a 3 de 4. Tercera ronda A ahora tiene ganancia 0,05 y B 0,0667, por lo que se asigna a B. Así, en cada paso elegimos la máxima mejora marginal y el resultado final maximiza el promedio.

Sobre la aparente doble contabilidad

El cálculo de la ganancia es una proyección y no implica añadir realmente al estudiante en esa etapa. Se define como Gainpass,total igual a Ratiopass + 1, total + 1 menos Ratiopass, total. Es un qué pasaría si para priorizar correctamente cuál clase debe recibir el siguiente estudiante.

Complejidad

Cada extracción e inserción en la cola cuesta Olog n y se realizan aproximadamente n cargas iniciales más k asignaciones, por lo que la complejidad total es O(n + k) log n en tiempo y O(n) en espacio.

Código C# resumido

public class Solution { public double MaxAverageRatio(int[][] classes, int extraStudents) { var pq = new PriorityQueue<(int pass, int total), double>(Comparer<double>.Create((a, b) => b.CompareTo(a))); foreach (var cls in classes) { var pass = cls[0]; var total = cls[1]; pq.Enqueue((pass, total), Gain(pass, total)); } for (var i = 0; i < extraStudents; i++) { var (pass, total) = pq.Dequeue(); pass++; total++; pq.Enqueue((pass, total), Gain(pass, total)); } double sum = 0; while (pq.Count > 0) { var (pass, total) = pq.Dequeue(); sum += CalculateRatio(pass, total); } return sum / classes.Length; } double CalculateRatio(int pass, int total) { return (double)pass / total; } double Gain(int pass, int total) { var current = CalculateRatio(pass, total); var after = CalculateRatio(pass + 1, total + 1); return after - current; } }

Cómo puede ayudarte Q2BSTUDIO

En Q2BSTUDIO somos una empresa de desarrollo de software con foco en aplicaciones a medida y software a medida, especialista en inteligencia artificial, ciberseguridad, servicios cloud AWS y Azure, servicios inteligencia de negocio y power bi, automatización de procesos, agentes IA e ia para empresas. Integramos patrones eficientes como colas de prioridad y técnicas greedy en soluciones reales para optimizar asignaciones, recursos y costes. Si buscas potenciar tus productos con modelos y algoritmos avanzados, descubre nuestros servicios de inteligencia artificial o cuéntanos tu reto para construir contigo una plataforma robusta de software a medida.

Conclusión

La clave de LeetCode 1792 está en comparar ganancias marginales y elegir siempre la mayor con una cola de prioridad. Este patrón es muy útil más allá de los problemas de entrevista y forma parte de muchas soluciones de optimización que diseñamos para productos escalables, seguros y listos para la nube.