Para que el número de casas sea lo más mínimo posible, se debe compartir el número máximo de casas entre los puntos.
Pero si la distancia entre dos puntos es mayor que 2K, entonces no pueden compartir la misma casa.
Ahora para proceder con la solución:
Pensemos que solo hay un punto
Así que somos libres de elegir un punto en el rango de K, ya sea a la izquierda o a la derecha.
no de casa no puede ser inferior a 1.
- ¿Qué son los problemas NP-completos? ¿Cómo podemos resolverlos?
- Cómo hacer una matriz de entradas de usuario en JavaScript
- ¿Qué es un algoritmo para aprender nuevos lenguajes de programación?
- Cómo implementar la idea de algoritmos en MATLAB
- Tiene una lista vinculada en la que cada nodo es otra lista vinculada. ¿Cómo encuentra el elemento Kth más exclusivo entre todos los nodos en el momento más óptimo?
Ahora si hay dos puntos.
O esos dos tendrán la casa más cercana individual o compartirán la casa en el mismo punto.
Ahora, mientras seleccionamos el punto de la casa para p [o], lo colocaremos a una distancia K tal que haya una posibilidad máxima de que se encuentre en la región de p [1].
Del mismo modo, podemos construir sobre esta idea.
Entonces el algoritmo es.
1. Ordenar todos los puntos.
2. inicializar housePoint = -infinity
3. para (i de 0 a n-1)
Compruebe si (p [i] – housePoint) <= k
si es verdad i ++
más
crear una nueva casa en housePoint = p [i] + k y aumentar houseCount
