Pista 1

Si pruebas un largo \(X\), puedes obtener

\[ \text{tramos}(X)=\sum_{i=1}^{n}\left\lfloor \frac{a_i}{X}\right\rfloor. \]

Si \(tramos(X) \ge K\), entonces \(X\) es posible; si no, \(X\) es demasiado grande.

Pista 2

La condición "\(tramos(X) \ge K\)" es monótona, así que puedes hacer búsqueda binaria en \(X\) (reales) entre \(0\) y \(max(a_i)\) con iteraciones fijas.

Solución

1. Modelar el problema

Tienes longitudes \(a_1, a_2, \dots, a_n\) y quieres encontrar el máximo largo \(X\) tal que, al cortar todas las tiras en pedazos de largo \(X\), puedas obtener al menos \(K\) pedazos.

Si eliges un largo \(X\), el número de tramos que puedes sacar es:

\[ \text{tramos}(X)=\sum_{i=1}^n \left\lfloor \frac{a_i}{X} \right\rfloor. \]

• Si \(tramos(X) \ge K\), ese largo sí es posible.
• Si \(tramos(X) < K\), ese largo es demasiado grande.

Esta función de factibilidad es monótona:

• Si un cierto \(X\) funciona, entonces cualquier \(X' \le X\) también funciona.
• Si \(X\) no funciona, cualquier \(X' \ge X\) tampoco.

Esto permite aplicar búsqueda binaria.

2. Búsqueda binaria sobre reales

Tomamos:

• Límite inferior: \(lo = 0\).
• Límite superior: \(hi = max(a_i)\) (no tiene sentido pedir un tramo más largo que la tira más larga).

Repetimos un número fijo de iteraciones (por ejemplo \(70\), suficiente para buen error):

1. \(mid = (lo + hi) / 2\)
2. Calculamos \(cnt = sum floor(a_i / mid)\)
3. Si \(cnt \ge K\), entonces \(mid\) es posible $\Rightarrow$ \(lo = mid\).
4. Si \(cnt < K\), entonces \(mid\) es grande $\Rightarrow$ \(hi = mid\).

Al final, \(lo\) queda como la mejor aproximación al largo máximo.

Implementación en C++

Las_Luces_de_la_Posada.cpp

Complejidad

Cada verificación (\(ok\)) recorre las \(N\) tiras, así que cuesta \(O(N)\).
Hacemos un número fijo de iteraciones (por ejemplo \(70\)), por lo que el total es:

\[ O(N\cdot \text{iteraciones}) \approx O(N), \]

o de forma equivalente, \(O(N\log(\text{precisión}))\) cuando se expresa en función del error objetivo.