.png)
Resolviendo LeetCode hasta estar en el top 1 por ciento — Día 73
Problema: 1792 Maximum Average Pass Ratio en LeetCode ver en LeetCode
Dificultad: Media
Etiquetas: Greedy, Heap, Matemáticas, Priority Queue
Resumen del problema
Tienes n clases. Cada clase tiene p alumnos aprobados de un total t. Dispones de extraStudents alumnos adicionales que siempre aprobarán. Puedes asignarlos uno a uno a cualquier clase. Objetivo: distribuirlos para maximizar el promedio de ratios de aprobados entre todas las clases.
Idea y razonamiento
Enfoque fuerza bruta: probar todas las distribuciones posibles explota combinatoriamente, ya que el número de formas crece como n elevado a extraStudents.
Enfoque óptimo con avaricia greedy: añadir un alumno a distintas clases aporta beneficios desiguales al promedio. La clave es medir el incremento marginal que aporta un alumno en cada clase y siempre elegir la clase con mayor ganancia en cada paso.
Función de ganancia
Para una clase con p aprobados y t en total, la ganancia de añadir un alumno que aprueba es: gain p, t = (p+1) dividido entre (t+1) menos p dividido entre t
Intuición
Antes de añadir el alumno, el ratio es p dividido entre t. Después es p mas 1 dividido entre t mas 1. La diferencia es la mejora exacta que esa clase aporta al promedio si recibe el siguiente alumno. Para maximizar el promedio total, en cada iteración asignamos el alumno a la clase con mayor ganancia. Esto se implementa eficientemente con un heap de máximos almacenando las ganancias marginales.
Algoritmo
1. Calcular la ganancia inicial para cada clase y meterla en un heap de máximos junto con p y t.
2. Repetir extraStudents veces extraer la clase con mayor ganancia, actualizarla sumando uno a p y t, recalcular su ganancia y devolverla al heap.
3. Al final, promediar los ratios p dividido entre t de todas las clases.
Complejidad
Tiempo: O de n mas extraStudents por log n, ya que cada inserción y extracción del heap cuesta log n y hacemos n inicializaciones mas extraStudents asignaciones.
Espacio: O de n por el heap.
Puntos clave
La función de ganancia es el insight central para cuantificar el beneficio marginal.
Un heap de máximos permite seleccionar siempre la mejor clase de forma eficiente.
Muchos problemas de asignación se resuelven con el patrón medir ganancia marginal, elegir máximo, actualizar.
Autorrevisión
Entendimiento del porqué: la mejora marginal es decreciente y avaricia por ganancia local maximiza el promedio global con heap.
Capacidad de recuerdo: alta, es un patrón clásico de avaricia con cola de prioridad.
Aplicación práctica y conexión con Q2BSTUDIO
En Q2BSTUDIO aplicamos este tipo de estrategias de optimización en proyectos reales de software a medida y aplicaciones a medida, desde asignación de recursos hasta scheduling inteligente. Si tu empresa busca construir soluciones eficientes con datos y algoritmos, nuestro equipo puede diseñar, desarrollar y desplegar la solución end to end. Conoce más sobre cómo creamos plataformas robustas y escalables en nuestro servicio de desarrollo de software y aplicaciones a medida.
Además, somos especialistas en inteligencia artificial e ia para empresas. Desde modelos de clasificación y recomendación hasta agentes IA con razonamiento y planificación incremental tipo heap, integramos estas capacidades con servicios cloud aws y azure, ciberseguridad y gobierno del dato. Descubre cómo impulsamos tu estrategia con IA en nuestra página de inteligencia artificial.
Palabras clave que trabajamos y entregamos en proyectos reales
software a medida, aplicaciones a medida, inteligencia artificial, ciberseguridad, servicios cloud aws y azure, servicios inteligencia de negocio, ia para empresas, agentes IA, power bi
Progreso personal
Día 73
Problemas resueltos totales 434
Confianza de hoy Alta
LeetCode rating 1530
Conclusión
El truco para Maximum Average Pass Ratio es priorizar por ganancia marginal con un heap. Este patrón es reutilizable en optimización de promedios, planificación de recursos y mejora iterativa en múltiples dominios de negocio. Si deseas llevar este tipo de enfoques a tus productos digitales con calidad empresarial y seguridad, en Q2BSTUDIO combinamos ingeniería de software a medida, agentes IA, servicios cloud y analítica con power bi para crear valor real y sostenible.
