Aggressive Cows
Un granero tiene establos a lo largo de una línea recta, y stalls[i] es la posición del establo i. Todas las posiciones son distintas y aparecen en un orden cualquiera. Debes colocar k vacas en k establos diferentes, y las vacas se pelean cuando están cerca, así que quieres que las dos vacas más cercanas estén lo más separadas posible.
Devuelve el mayor valor posible de la distancia mínima entre dos vacas cualesquiera.
Función
- stallsinteger-array
- las distintas posiciones de los puestos, en cualquier orden
- kinteger
- el número de vacas que colocar
- Devuelveinteger
- la mayor distancia mínima posible entre dos vacas
Restricciones
2 ≤ stalls.length ≤ 50000 ≤ stalls[i] ≤ 109- Todas las posiciones en
stallsson distintas. 2 ≤ k ≤ stalls.length
Ejemplos
- Entrada
- stalls = [10, 1, 7, 4, 15]k = 3
- Salida
- 6
- Explicación
- Las vacas en 1, 7 y 15 están separadas por 6 y 8. Una distancia de 7 no funciona: después de 1, la siguiente vaca va a 10, y no hay ningún puesto en 17 o más allá.
- Entrada
- stalls = [9, 3, 20, 5]k = 4
- Salida
- 2
- Explicación
- Cuatro vacas y cuatro establos significa que cada establo recibe una vaca. Ordenados, los establos son 3, 5, 9 y 20, y los vecinos más cercanos, 3 y 5, están separados por 2.
- Entrada
- stalls = [14, 2, 30, 22, 8]k = 2
- Salida
- 28
- Explicación
- Las dos vacas están mejor en los dos extremos de la línea. Los puestos van del 2 al 30, así que las vacas quedan separadas por 28.
Para ir más allá
¿Qué cambia si los puestos están dispuestos en un círculo, de modo que el último puesto en el orden también sea vecino del primero?
Pistas
Ábrelas de una en una. Cada una revela un poco más.
Deja a un lado por un momento la mejor respuesta. Si alguien te da una distancia
g, ¿puedes decidir si cabenkvacas con al menosgde separación entre cada dos?Ordena los puestos y coloca las vacas desde la izquierda, cada una en el primer puesto que esté al menos a
gde distancia de la vaca anterior. Si una distancia funciona, también funciona cualquier distancia menor.Busca mediante búsqueda binaria
gentre 1 y la distancia entre los puestos dividida pork-1. Conserva la mayor distancia para la que el algoritmo voraz coloca al menoskvacas.
Solución
Fija una distancia y pregunta: ¿pueden ubicarse k vacas de modo que cada par esté separado al menos por esa distancia? Una pasada voraz por los puestos ordenados responde a esta pregunta. La respuesta cambia de sí a no una vez a medida que aumenta la distancia, así que la búsqueda binaria encuentra el último sí.
Ordena y luego prueba cada intervalo por turno
Correcto, pero no termina con las pruebas más grandes
Intuición
Ordena las posiciones. Las dos vacas más cercanas siempre son vecinas, así que una distancia g funciona cuando cada par de vacas vecinas está separado por al menos g.
Para probar una distancia, coloca una vaca en el establo más a la izquierda y luego otra en cada establo que esté al menos a g del último. Esta colocación voraz permite ubicar tantas vacas como cualquier otra colocación. Alinea desde la izquierda cualquier colocación válida: la vaca i de la colocación voraz nunca queda a la derecha de la vaca i de esa colocación, así que la colocación voraz encuentra un establo para su siguiente vaca no más tarde.
Una distancia de 1 siempre funciona, así que prueba g = 2, 3, ... y detente en la primera distancia que ubique menos de k vacas. En el primer ejemplo, una distancia de 6 ubica 3 vacas y una de 7 solo 2, así que la respuesta es 6.
Con dos vacas y establos en 0 y 10^9, eso supone aproximadamente 10^9 recorridos de 5000 establos, es decir, 5 × 10^12 pasos.
Algoritmo
- Ordena las posiciones.
- Escribe la comprobación para una separación
g: una vaca enpos[0], luego una vaca en cada establo dondepos[i] - last ≥ g, contando las vacas. - Empieza con
gap = 1. - Mientras la comprobación para
gap + 1coloque al menoskvacas, suma 1 agap. - Devuelve
gap.
def cowsPlaced(pos, gap):
count, last = 1, pos[0] # the first cow takes the leftmost stall
for p in pos[1:]:
if p - last >= gap:
count += 1
last = p
return count
def aggressiveCows(stalls, k):
pos = sorted(stalls)
gap = 1 # positions are distinct, so a gap of 1 always fits every cow
while cowsPlaced(pos, gap + 1) >= k:
gap += 1
return gapBúsqueda binaria en el intervalo
Intuición
Una colocación en la que cada separación sea de al menos g+1 también tiene cada separación de al menos g, así que las comprobaciones dan sí, ..., sí, no, ..., no. La búsqueda binaria encuentra el último sí.
Busca desde lo = 1, que siempre funciona, hasta hi = la distancia dividida entre k-1, redondeada hacia abajo: k vacas dejan k-1 separaciones dentro de la distancia, así que la menor no puede ser mayor. Una comprobación satisfactoria establece lo = mid, por lo que mid debe redondearse hacia arriba; redondeando hacia abajo, lo = 5 y hi = 6 se repiten para siempre.
En el primer ejemplo, la distancia es 14 y k = 3, así que hi = 7. La separación 4 pasa, la separación 6 pasa, la separación 7 falla y el rango se cierra en 6.
Un rango de hasta 10^9 de ancho se cierra en unas 30 comprobaciones de 5000 establos, aproximadamente 150 000 pasos.
Algoritmo
- Ordena las posiciones.
- Establece
lo = 1yhi = (pos[n-1] - pos[0]) / (k-1), redondeado hacia abajo. - Mientras
lo < hi, calculamid = lo + (hi - lo + 1) / 2. - Si la comprobación voraz en
midcoloca al menoskvacas, establecelo = mid; de lo contrario, establecehi = mid - 1. - Devuelve
lo.
def cowsPlaced(pos, gap):
count, last = 1, pos[0] # the first cow takes the leftmost stall
for p in pos[1:]:
if p - last >= gap:
count += 1
last = p
return count
def aggressiveCows(stalls, k):
pos = sorted(stalls)
lo = 1 # positions are distinct, so a gap of 1 always works
hi = (pos[-1] - pos[0]) // (k - 1) # k-1 gaps share the whole span
while lo < hi:
mid = lo + (hi - lo + 1) // 2 # round up so lo = mid always moves
if cowsPlaced(pos, mid) >= k:
lo = mid # mid fits, so the answer is mid or larger
else:
hi = mid - 1 # mid does not fit, so the answer is smaller
return lo
Errores comunes y casos límite
- Omitir la ordenación. En
[10, 1, 7, 4, 15]sin ordenar y con una distancia de 6, la comprobación empieza en 10, no encuentra ningún establo posterior que esté al menos a 6 de distancia y devuelve una vaca. - Redondear
midhacia abajo mientras una pasada establecelo = mid. Cuandohi = lo + 1, el rango deja de reducirse y el bucle nunca termina. - Comprobar si hay exactamente
kvacas. Con una distancia de 1, el primer ejemplo coloca 5 vacas, más de 3, y aun así la distancia funciona; compruebacount ≥ k. - Empezar el recuento de vacas en 0. La vaca del establo más a la izquierda cuenta, así que el recuento empieza en 1.
Preguntas frecuentes3
¿Cuál es la complejidad temporal de Aggressive Cows?
La ordenación tarda O(n log n) y la búsqueda binaria O(n log D), donde D es la extensión de los puestos dividida por k-1. Además de una copia ordenada, la memoria es O(1).
¿Por qué la primera vaca siempre va al establo de más a la izquierda?
Toma cualquier ubicación que funcione y mueve su vaca más a la izquierda al establo más a la izquierda. Esa vaca solo se aleja de las demás, así que ninguna distancia disminuye, y alguna ubicación óptima usa el establo más a la izquierda.
¿Cómo identificas una búsqueda binaria sobre la respuesta?
La pregunta pide el valor más grande o más pequeño para el que algo es posible; comprobar un valor es mucho más fácil que encontrar el mejor, y las respuestas cambian solo una vez a medida que aumenta el valor. Aquí, el valor es la separación y la comprobación consiste en la colocación voraz.
Problemas similares
Problemas que usan las mismas ideas. Resolver dos o tres es lo que fija un patrón.
def aggressiveCows(stalls, k):
# Escribe el código aquíPrueba #1
Prueba #2
Prueba #3
Argumentos
stalls = [10, 1, 7, 4, 15] k = 3
Salida Esperada
6