Firehose

Explicación

Sea $\texttt{possible}(i)$ verdadero si es posible conectar una casa a al menos un hidrante tras colocar $k$ hidrantes de modo que la longitud de cada manguera sea $i$ . Sabemos que si $\texttt{possible}(i)$ es verdadero, $\texttt{possible}(i + 1)$ también lo es, porque un aumento en la longitud de la manguera no impide construir una configuración válida de hidrantes. En consecuencia, $\texttt{possible}(i)$ es monótono, y podemos hacer búsqueda binaria del menor valor de $i$ tal que $\texttt{possible}(i)$ sea verdadero.

Usamos un algoritmo voraz para hallar $\texttt{possible}(i)$ . Primero, queremos ordenar todas las casas por su dirección. Para cada $j$ de $1...n$ , sea $h_j$ la dirección de la $j$ -ésima casa. Colocamos un hidrante en la dirección $h_j + i$ , y este hidrante cubrirá todas las casas en el rango $[h_j, h_j + 2i]$ . Podemos repetir este proceso para la primera casa a la derecha cuya dirección no caiga en este rango hasta que cada casa se pueda conectar con al menos un hidrante. Nótese que, por la naturaleza circular de la calle, hay que hacer todos los cálculos $\bmod 1000000$ . Si la cantidad de hidrantes necesaria es mayor que la cantidad de hidrantes permitida, $\texttt{possible}(i)$ es falso; en caso contrario, es verdadero.

Implementación

Complejidad temporal: $\mathcal O(h^2\times log(\texttt{max}(H_i)))$

C++JavaPython


#include <bits/stdc++.h>
using namespace std;
 
const int MAX_H = 1000;
const int STREET_SIZE = 1000000;
 
int num_houses;
int num_hydrants;
int houses[MAX_H];
 
bool possible(int length) {
	for (int i = 0; i < num_houses; i++) {
		// Cantidad de hidrantes que se necesitan.
		int needed = 0;
 
		// La casa a la que hay que conectar un hidrante.
		int start = houses[i];
 
		for (int j = 1; j < num_houses; j++) {
			// Dirección de la casa en el índice j.
			int end = houses[(i + j) % num_houses];
 
			/*
			 * Si la distancia entre las casas de inicio y fin es mayor que
			 * dos veces la longitud de la manguera, un solo hidrante no
			 * alcanzará para cubrir ambas casas.
			 */
			int dist = (end - start + STREET_SIZE) % STREET_SIZE;
			if (dist > 2 * length) {
				start = end;
				needed++;
			}
		}
 
		// Incrementamos needed porque hace falta otro hidrante para llegar a las últimas casas.
		needed++;
 
		if (needed <= num_hydrants) { return true; }
	}
	return false;
}
 
int main() {
	cin >> num_houses;
	for (int i = 0; i < num_houses; i++) { cin >> houses[i]; }
	cin >> num_hydrants;
 
	sort(houses, houses + num_houses);
 
	// Búsqueda binaria de la menor longitud de manguera
	int l = 0;
	int r = STREET_SIZE;
	int ans = -1;
	while (l <= r) {
		int m = (l + r) / 2;
		if (possible(m)) {
			r = m - 1;
			ans = m;
		} else {
			l = m + 1;
		}
	}
 
	cout << ans << endl;
}


import java.io.*;
import java.util.*;
 
public class Firehose {
	private static final int MAX_H = 1000;
	private static final int STREET_SIZE = 1000000;
 
	private static boolean possible(int length, int numHydrants, int[] houses) {
		for (int i = 0; i < houses.length; i++) {
			int needed = 0;  // Cantidad de hidrantes que se necesitan.
			// La casa a la que hay que conectar un hidrante.
			int start = houses[i];
			for (int j = 1; j < houses.length; j++) {
				// Dirección de la casa en el índice j.
				int end = houses[(i + j) % houses.length];
				/*
				 * Si la distancia entre las casas de inicio y fin es mayor que
				 * dos veces la longitud de la manguera, un solo hidrante no
				 * alcanzará para cubrir ambas casas.
				 */
				int dist = (end - start + STREET_SIZE) % STREET_SIZE;
				if (dist > 2 * length) {
					start = end;
					needed++;
				}
			}
 
			// Incrementamos needed porque hace falta otro hidrante para llegar a las últimas casas.
			needed++;
 
			if (needed <= numHydrants) { return true; }
		}
		return false;
	}
 
	public static void main(String[] args) {
		Kattio io = new Kattio();
 
		int numHouses = io.nextInt();
		int[] houses = new int[numHouses];
 
		for (int i = 0; i < numHouses; i++) { houses[i] = io.nextInt(); }
 
		int numHydrants = io.nextInt();
 
		Arrays.sort(houses);
 
		// Búsqueda binaria de la menor longitud de manguera
		int left = 0;
		int right = STREET_SIZE;
		int ans = -1;
		while (left <= right) {
			int mid = (left + right) / 2;
			if (possible(mid, numHydrants, houses)) {
				right = mid - 1;
				ans = mid;
			} else {
				left = mid + 1;
			}
		}
 
		System.out.println(ans);
		io.close();
	}
 
	// CodeSnip{Kattio}
}


MAX_H = 1000
STREET_SIZE = 1000000
 
 
def possible(length: int, num_hydrants: int, houses: list) -> bool:
	for i in range(len(houses)):
		# Cantidad de hidrantes que se necesitan.
		needed = 0
		# La casa a la que hay que conectar un hidrante.
		start = houses[i]
		for j in range(1, len(houses)):
			# Dirección de la casa en el índice j.
			end = houses[(i + j) % len(houses)]
 
			"""
			Si la distancia entre las casas de inicio y fin es mayor que
			dos veces la longitud de la manguera, un solo hidrante no
			alcanzará para cubrir ambas casas.
			"""
			dist = (end - start + STREET_SIZE) % STREET_SIZE
			if dist > 2 * length:
				start = end
				needed += 1
 
		# Incrementamos needed porque hace falta otro hidrante para llegar a las últimas casas.
		needed += 1
 
		if needed <= num_hydrants:
			return True
 
	return False
 
 
num_houses = int(input())
houses = []
for _ in range(num_houses):
	houses.append(int(input()))
 
num_hydrants = int(input())
 
houses.sort()
 
# Búsqueda binaria de la menor longitud de manguera
l = 0
r = STREET_SIZE
ans = -1
while l <= r:
	m = (l + r) // 2
	if possible(m, num_hydrants, houses):
		r = m - 1
		ans = m
	else:
		l = m + 1
 
print(ans)