12 · Búsqueda binaria sobre la respuesta
Buscar soluciones eficientes · Ruta de Aprendizaje
Antes de empezar. El intervalo y sus límites en 08 - Búsqueda binaria.
🎯 Objetivos
Al terminar este módulo sabes:
- Reconocer la monotonía FFFF…TTTT en un problema (aunque no haya ningún arreglo).
- Escribir el combo
check(x)+ búsqueda del “primer SÍ”. - Atacar los patrones “minimizar el máximo” y “maximizar el mínimo”.
📖 La lección
La gran idea
Dos máquinas completan un producto cada 2 y 3 segundos, respectivamente. Queremos fabricar al menos 7 productos en el menor tiempo posible. Probar tiempos pequeños nos permite ver la pregunta que hay que responder:
| Segundos | Productos entre ambas | ¿Alcanza 7? |
|---|---|---|
| 6 | 3 + 2 = 5 | no |
| 8 | 4 + 2 = 6 | no |
| 9 | 4 + 3 = 7 | sí |
| 10 | 5 + 3 = 8 | sí |
Cada máquina termina t / k[i] productos, usando división entera: uno que
está a medio fabricar todavía no cuenta. Si 9 segundos alcanzan, esperar
más no quita productos. Por eso las respuestas forman NO…NO, SÍ…SÍ.
Llamamos monotonía a esa propiedad: el sí no vuelve a convertirse en no.
Si el diagrama no cabe, deslízalo horizontalmente.
En la búsqueda de un arreglo descartábamos valores por su orden. Aquí buscamos el primer tiempo suficiente: un no descarta ese tiempo y todos los menores; un sí conserva ese tiempo como candidato y descarta los mayores. No hace falta guardar un arreglo con todos los tiempos.
La plantilla del “primer SÍ”
Primero escribamos solo el chequeo, sin búsqueda. Suponemos al menos una
máquina, 1 <= k[i] <= 10⁹ y 1 <= objetivo <= 10⁹.
int n, objetivo;
vector<long long> k; // globales: ambas funciones usan la misma entrada
bool alcanza(long long t) {
long long hechos = 0;
for (int i = 0; i < n; i++) {
hechos += t / k[i];
if (hechos >= objetivo) return true;
}
return false;
}alcanza(8) devuelve falso y alcanza(9) verdadero en el ejemplo. Usaremos
tiempos entre 0 y 10¹⁸. El corte mantiene hechos < objetivo antes de cada
suma; al añadir como máximo 10¹⁸, el resultado cabe en long long.
Buscar sin perder la respuesta
Necesitamos un intervalo que contenga el mínimo. El tiempo 1 es una cota
inferior. La última máquina, trabajando sola, completa el objetivo en
k.back() * objetivo: es una cota superior suficiente. En el ejemplo es
3·7=21. Bajo las cotas declaradas ese producto no supera 10¹⁸.
| lo | hi | medio | ¿Alcanza? | Intervalo siguiente |
|---|---|---|---|---|
| 1 | 21 | 11 | sí: 5+3=8 | [1,11] |
| 1 | 11 | 6 | no: 3+2=5 | [7,11] |
| 7 | 11 | 9 | sí: 4+3=7 | [7,9] |
| 7 | 9 | 8 | no: 4+2=6 | [9,9] |
Si medio sirve, podría ser la respuesta: no lo eliminamos. Si no sirve,
ni él ni un tiempo menor pueden servir. Esa es la razón de las dos
actualizaciones, no una regla que haya que memorizar sin entender:
// usa: alcanza, k, objetivo
long long menor_tiempo() {
long long lo = 1, hi = k.back() * objetivo;
while (lo < hi) {
long long medio = lo + (hi - lo) / 2;
if (alcanza(medio)) hi = medio;
else lo = medio + 1;
}
return lo;
}Ambas funciones van antes de main, con n, k y objetivo como variables
globales. Después de leerlos en main, imprime menor_tiempo(). La traza y
el código usan exactamente la misma cota. Al terminar, queda un solo candidato.
Cada vuelta reduce el intervalo; para una cota de 10¹⁸ bastan unas 60 vueltas.
Cada chequeo visita hasta n máquinas: O(n log rango) tiempo y O(1) memoria
adicional al vector de tiempos. Si cambian las restricciones, vuelve a
justificar las cotas y el rango de las operaciones.
La ficha Búsqueda binaria sobre la respuesta reúne las condiciones del patrón; Búsqueda Binaria compara primer y último sí.
El último SÍ: separar dos objetos
Tenemos posiciones {0,3,7} y queremos elegir dos con la mayor separación posible. Para dos objetos basta restar los extremos: no necesitamos una búsqueda para resolverlo. Usaremos cabe(d), equivalente a 7−0 >= d, solo para entender la plantilla espejo. Al pedir más objetos habrá que diseñar y demostrar otro chequeo.
Para d de 0 a 8 las respuestas son S S S S S S S S N. Si una separación es posible, una menor también: buscamos el último SÍ, a diferencia de las máquinas, donde buscamos el primero.
int lo = 0, hi = 8;
while (lo < hi) {
int medio = lo + (hi - lo + 1) / 2;
bool cabe = 7 >= medio;
if (cabe) lo = medio;
else hi = medio - 1;
}
cout << lo << "\n"; // 7| lo | hi | medio (hacia arriba) | resultado | intervalo siguiente |
|---|---|---|---|---|
| 0 | 8 | 4 | sí | [4,8] |
| 4 | 8 | 6 | sí | [6,8] |
| 6 | 8 | 7 | sí | [7,8] |
| 7 | 8 | 8 | no | [7,7] |
Con dos candidatos, redondear hacia abajo repetiría medio=lo y lo=medio no avanzaría. Redondear hacia arriba permite descartar al menos uno. El intervalo debe contener una respuesta factible; aquí 0 lo es.
Cuando el chequeo sí necesita decisiones
Ahora hay posiciones {0,3,7,10} y debemos elegir tres objetos con
separación entre consecutivos de al menos d. Para d=3 podemos tomar 0,3,7;
para d=4, tomar 0,7 deja sin espacio al tercero.
El chequeo coloca el primero en la posición más a la izquierda y cada siguiente en la primera posición que esté al menos d más allá. Esto deja tanto espacio como sea posible para los que faltan: sustituir una colocación por otra más a la izquierda no empeora las opciones siguientes. Aplicando ese argumento a cada elección, si el chequeo no logra colocar los tres, ninguna colocación lo logra. Aquí el último sí es 3. Las posiciones deben estar ordenadas, y disminuir d nunca vuelve imposible una colocación válida.
Los disfraces clásicos
- “Minimizar el máximo”: reparte n cosas en k grupos minimizando el grupo
más cargado →
check(x): “¿se puede con ningún grupo sobre x?”. - “Maximizar el mínimo”: coloca k objetos lo más separados posible →
check(d): “¿caben con separación mínima d?”. - “El mínimo x tal que…”: casi cualquier enunciado con esa frase.
Cuando veas esas frases, tu primer reflejo debe ser “¿es monótono el check?”. También debes demostrar que el chequeo es correcto y suficientemente rápido.
Si el predicado no es monótono, estas plantillas no están justificadas. La Búsqueda ternaria estudia otro caso: optimizar una función objetivo unimodal (por ejemplo, que primero decrece y luego crece). No basta con que una pregunta de sí/no falle la condición de monotonía.
Completar las herramientas básicas de Regional
Antes de pasar a un simulacro Regional, sigue estas dos lecturas breves:
- Prefijos en una dimensión, y luego ventana con números positivos. Puedes dejar los rectángulos y la práctica avanzada para después.
- Selección de actividades, incluyendo el argumento de intercambio que sigue. Solo necesitas ordenar pares; las otras estrategias y comparaciones exhaustivas pueden esperar.
Son herramientas de arreglos y ordenamiento: no requieren estudiar antes los módulos de grafos ni programación dinámica. Tras esas secciones, continúa con Simulacros o vuelve al orden principal de la ruta.
🏋️ Práctica
Práctica directa: Buscar ambas fronteras
Con máquinas de tiempos 2 y 3 y objetivo 7, calcula el primer tiempo suficiente: 9. Con posiciones {0,3,7} y dos objetos, calcula la última separación factible: 7.
Idea para comprobar tu solución
En máquinas la franja es NO…SÍ; en separación es SÍ…NO. Justifica qué lado conserva la respuesta antes de copiar una plantilla.
Variación: Un límite de capacidad
Hay paquetes en orden con pesos {4,2,5,1}. Debes dividirlos en a lo más dos grupos contiguos no vacíos, minimizando el mayor peso total de un grupo. La respuesta es 6.
Una pista, si la necesitas
Para una capacidad fija, ¿puedes formar grupos sin superar ese límite?
Contrastar el razonamiento
Con pesos positivos, llena cada grupo hasta que el siguiente paquete exceda la capacidad. Ese chequeo usa el mínimo número de grupos: ningún primer grupo válido puede acabar más tarde. Capacidad 5 requiere cuatro grupos (
{4},{2},{5},{1}); 6 admite{4,2}y{5,1}. El primer SÍ está entre el mayor peso y la suma total.
Aplicar en problemas
Los problemas siguientes requieren traducir un enunciado y pueden combinar otras ideas. Su procedencia e idioma no indican un orden obligatorio de dificultad.
Problemas OCI reales, en español (cada nota trae el link a su mirror):
| # | Problema | Fase | Qué practica |
|---|---|---|---|
| 1 | Teletransportador cuántico | Clasificatoria 2017 | ampliación: costo convexo; requiere justificar otra condición de búsqueda |
| 2 | La leyenda de Zolda II | Nacional 2017 | binaria sobre el radio contando puntos |
Más aplicaciones (en inglés)
| # | Problema | Dificultad | Qué practica |
|---|---|---|---|
| 1 | K-divisible Sum (1476A) | ★★ (1000) | el mínimo factible (¿hace falta la binaria?) |
| 2 | Building an Aquarium (1873E) | ★★ (1100) | binaria sobre la altura del agua |
| 3 | Factory Machines (CSES 1620) | ★★★ (—) | LA clásica de este módulo (la de la lección) |
| 4 | Array Division (CSES 1085) | ★★★ (—) | minimizar el máximo |
| 5 | ⭐ Poisoned Dagger (1613C) | ★★★ (1200) | binaria sobre la duración del veneno |
Un ejemplo para pensar
Una máquina termina un producto cada cuatro segundos. Queremos obtener
al menos dos. ¿Sería equivalente definir check(t) como «produce
exactamente dos» en vez de «produce al menos dos»?
La pregunta debe conservar el SÍ al aumentar el tiempo
«Al menos dos» es falso hasta el segundo 7 y verdadero desde el 8: esperar más nunca invalida una solución. «Exactamente dos» solo es verdadero del segundo 8 al 11; desde el 12 vuelve a ser falso. Esa segunda pregunta no tiene la forma FFFF…TTTT que necesita la plantilla del primer SÍ, aunque su primer tiempo verdadero coincida. La monotonía pertenece al
checkelegido, no solo a la historia del problema.
← 11 - Colas de prioridad · Ruta de Aprendizaje · 13 - Backtracking →