Koko Eating Bananas
Koko tiene n montones de plátanos, donde piles[i] es la cantidad de plátanos en el montón i, y faltan h horas para que vuelvan los guardias. Elige una velocidad para comer k, un número entero de plátanos por hora, y la mantiene. Cada hora come k plátanos de un montón; si quedan menos de k en ese montón, se lo termina y descansa hasta que acaba la hora. Devuelve la velocidad mínima k que le permite terminar todos los montones en un máximo de h horas.
Función
- pilesinteger-array
- el número de plátanos en cada montón
- hinteger
- la cantidad de horas que tiene Koko
- Devuelveinteger
- la menor velocidad de ingesta expresada en bananas por hora que permite terminar cada montón en un máximo de h horas
Restricciones
1 ≤ piles.length ≤ 50001 ≤ piles[i] ≤ 109piles.length ≤ h ≤ 109, por lo que siempre existe una respuesta.
Ejemplos
- Entrada
- piles = [4, 10, 7, 3]h = 6
- Salida
- 5
- Explicación
- A velocidad 5, las pilas 4, 10, 7 y 3 tardan 1, 2, 2 y 1 horas: 6 en total, lo que cabe. A velocidad 4 tardan 1, 3, 2 y 1 horas, que suman 7, una hora de más.
- Entrada
- piles = [30, 11, 23, 4, 20]h = 5
- Salida
- 30
- Explicación
- Cinco montones y cinco horas dejan exactamente una hora por montón, así que la velocidad debe permitir terminar el montón más grande, 30, en una hora. A una velocidad de 29, ese montón necesitaría una segunda hora.
- Entrada
- piles = [5, 9, 2]h = 20
- Salida
- 1
- Explicación
- A velocidad 1, las pilas tardan 5 + 9 + 2 = 16 horas, bastante menos de 20. No hay ninguna velocidad menor que 1, así que la respuesta es 1.
+22 pruebas ocultas al enviar
Para ir más allá
Un problema gemelo: Koko tiene d días y come montones enteros en el orden indicado, tantos montones al día como quepan dentro de un límite diario de k bananas. ¿Cuál es el menor k y qué dos partes de tu búsqueda binaria cambian?
Pistas
Ábrelas de una en una. Cada una revela un poco más.
Fija una velocidad
k. ¿Cuántas horas se tarda en comer una pila depbananas a esa velocidad, dado que Koko nunca cambia de pila dentro de una hora? ¿Cuántas horas se tarda en comer todas las pilas?Si la velocidad
ktermina a tiempo, también lo hace cualquier velocidad más rápida. Las velocidades que funcionan forman una secuencia ininterrumpida que comienza en la respuesta.Realiza una búsqueda binaria entre las velocidades de 1 y la pila más grande. Cuenta las horas a la velocidad intermedia en una sola pasada: si caben en
h, la respuesta es como máximo la velocidad intermedia; de lo contrario, es mayor.
Solución
La respuesta aquí es una velocidad, no una posición del arreglo, y eso oculta la búsqueda binaria. Comprobar una velocidad requiere recorrer las pilas una sola vez. Las comprobaciones también están ordenadas: si la velocidad k termina a tiempo, todas las velocidades mayores también lo hacen. Así que puedes hacer una búsqueda binaria entre las velocidades de 1 hasta la pila más grande y necesitas unas 30 comprobaciones, mientras que probar las velocidades una por una puede requerir mil millones.
Prueba todas las velocidades desde 1 en adelante
Correcto, pero no termina con las pruebas más grandes
Intuición
Empieza con una pregunta: ¿cuánto tarda un montón de p plátanos a una velocidad de k? Koko come k por hora y nunca pasa a otro montón dentro de la misma hora, así que el montón tarda p / k horas, redondeando hacia arriba. Un montón de 10 a una velocidad de 4 tarda 3 horas: 4, 4 y después 2, con una hora de descanso. Suma eso para todos los montones y compara el total con h.
Ahora prueba las velocidades en orden: 1, 2, 3, y así sucesivamente, y devuelve la primera cuyo total cabe en h. Es la menor por construcción, ya que se probaron todas las velocidades más lentas y no funcionaron. El bucle siempre se detiene: a la velocidad del montón más grande, cada montón tarda una hora, y h es al menos igual al número de montones.
El problema es hasta dónde puede llegar el bucle. Con 5000 montones de casi 10^9 plátanos y h = 5000, la respuesta se acerca a 10^9, así que el bucle se ejecuta cerca de mil millones de veces y cada comprobación lee los 5000 montones: unos 5 × 10^12 pasos. Aquí, m es el montón más grande.
Algoritmo
- Establece
speed = 1. - Cuenta las horas a esta velocidad: para cada montón, suma
(pile + speed-1) / speed, usando un total de 64 bits. - Si el total es como máximo
h, devuelvespeed. - De lo contrario, suma 1 a
speedy vuelve a contar.
def minEatingSpeed(piles, h):
speed = 1
while True:
hours = 0
for pile in piles:
hours += (pile + speed - 1) // speed # a started pile costs a whole hour
if hours <= h:
return speed
speed += 1Búsqueda binaria en la velocidad
Intuición
Piensa en cada velocidad del 1 a la pila más grande como una fila de respuestas a la pregunta «¿esta velocidad permite terminar a tiempo?». A medida que aumenta la velocidad, cada pila requiere la misma cantidad de horas o menos, así que el total solo puede disminuir. Por lo tanto, la fila muestra no, no, no y luego sí a partir de la respuesta, sin volver atrás. Buscas el primer sí, y una fila ordenada de no y sí es exactamente lo que la búsqueda binaria divide por la mitad.
Mantén un rango de lo a hi que siempre contenga la respuesta. Empieza en 1 y en la pila más grande, lo cual es seguro porque la velocidad de la pila más grande requiere una hora por pila y h es suficiente para eso. Comprueba la velocidad intermedia mid. Si alcanza, la respuesta es mid o una velocidad menor, así que establece hi = mid y conserva mid dentro del rango. Si no alcanza, todas las velocidades menores tampoco sirven, así que establece lo = mid + 1. Cuando lo llega a hi, esa velocidad es la respuesta.
Sigamos el primer ejemplo: pilas de 4, 10, 7 y 3 con h = 6. El rango va de 1 a 10. La velocidad 5 requiere 1 + 2 + 2 + 1 = 6 horas, así que alcanza y el rango pasa a ser de 1 a 5. La velocidad 3 requiere 2 + 4 + 3 + 1 = 10 horas, demasiadas, así que el rango pasa a ser de 4 a 5. La velocidad 4 requiere 1 + 3 + 2 + 1 = 7 horas, todavía demasiadas, así que el rango pasa a ser de 5 a 5 y la respuesta es 5.
Cada comprobación reduce el rango a la mitad, así que un rango de hasta 10^9 velocidades requiere unas 30 comprobaciones. Con 5000 pilas por comprobación, eso supone unos 150000 pasos en lugar de billones.
Algoritmo
- Establece
lo = 1yhien la pila más grande. - Mientras
lo < hi, tomamid = lo + (hi - lo) / 2. - Cuenta las horas a velocidad
mid: suma(pile + mid-1) / midpor cada pila, en un total de 64 bits. - Si el total es como máximo
h, establecehi = mid; de lo contrario, establecelo = mid + 1. - Cuando termine el bucle, devuelve
lo.
def minEatingSpeed(piles, h):
lo, hi = 1, max(piles) # the largest pile always works: one hour per pile
while lo < hi:
mid = lo + (hi - lo) // 2
hours = 0
for pile in piles:
hours += (pile + mid - 1) // mid
if hours <= h:
hi = mid # mid works, so the answer is mid or slower
else:
lo = mid + 1 # mid is too slow, so the answer is faster
return lo
Errores comunes y casos límite
La búsqueda en sí es breve. Los errores se esconden en el recuento de horas y en los extremos del intervalo.
- Desbordamiento del recuento de horas. A velocidad 1, 5000 montones de
10^9bananas tardan5 × 10^12horas, muy por encima del límite de 32 bits, de aproximadamente2.1 × 10^9. Un total desbordado puede resultar pequeño y permitir que pase la comprobación una velocidad demasiado baja. Cuenta con un entero de 64 bits o deja de contar en cuanto el total supereh. - Redondear en la dirección equivocada. La división entera redondea hacia abajo, por lo que
10 / 4da 2, pero ese montón tarda 3 horas. Redondea hacia arriba con(pile + k-1) / k. - Empezar el intervalo en 0. Entonces
midpuede ser 0 y el recuento de horas divide entre cero. La velocidad real más baja es 1. - Mover
hiamid - 1cuandomidcumple la condición. Eso puede descartar la respuesta misma. Cuando busques la primera velocidad que funciona, conservamidconhi = midy repite mientraslo < hi. - Empezar con
hipor debajo del montón más grande. Las velocidades inferiores pueden fallar todas cuandohes igual al número de montones, así que la búsqueda devolvería una velocidad que no funciona.
Preguntas frecuentes4
¿Cuál es la complejidad temporal de Koko Eating Bananas?
La búsqueda binaria se ejecuta en tiempo O(n log m), donde n es el número de montones y m es el montón más grande. Cada comprobación lee cada montón una vez, y el rango de velocidades se reduce a la mitad después de cada comprobación, así que hay aproximadamente log2(m) comprobaciones: 30 cuando m = 10^9. El espacio adicional es O(1).
¿Por qué funciona la búsqueda binaria con la velocidad de consumo?
La búsqueda binaria necesita una pregunta de sí o no cuyas respuestas estén ordenadas. «¿Puede Koko terminar a velocidad k?» es una: una velocidad mayor nunca necesita más horas, porque el resultado de redondear hacia arriba cada montón p / k solo puede disminuir a medida que k aumenta. Así que todas las velocidades inferiores a la respuesta fallan y todas las velocidades iguales o superiores tienen éxito, y la búsqueda encuentra el límite.
¿Cuáles son los límites inferior y superior de la velocidad?
El límite superior es la pila más grande: a esa velocidad cada pila tarda exactamente una hora, y h es al menos el número de pilas, así que siempre alcanza. Una velocidad mayor sigue requiriendo una hora por pila, por lo que buscar por encima no aporta nada. El límite inferior es 1, y puedes ajustarlo al número total de bananas dividido por h, redondeado hacia arriba, porque Koko come como máximo k bananas por hora.
¿Cómo se divide y se redondea hacia arriba con enteros?
Usa (p + k-1) / k con división entera. Sumar k-1 empuja cualquier resto hasta el siguiente múltiplo de k, y un múltiplo exacto permanece donde está: 10 a velocidad 4 da 13 / 4 = 3, y 8 a velocidad 4 da 11 / 4 = 2. Esto evita los números de punto flotante, donde los valores grandes pueden redondearse en la dirección incorrecta.
Problemas similares
Problemas que usan las mismas ideas. Resolver dos o tres es lo que fija un patrón.
Python
def minEatingSpeed(piles, h):
# Escribe el código aquíCaso 1
Caso 2
Caso 3
Entrada
piles = [4, 10, 7, 3] h = 6
Esperado
5