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:

SegundosProductos entre ambas¿Alcanza 7?
63 + 2 = 5no
84 + 2 = 6no
94 + 3 = 7sí
105 + 3 = 8sí

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.

¿Cuándo alcanzamos 7 productos?objetivo: 701N12N23N34N35N56N57N68N79S810StPrimer SÍ: 9 segundosDespués de alcanzar 7, esperar más sigue sirviendo.

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¹⁸.

lohimedio¿Alcanza?Intervalo siguiente
12111sí: 5+3=8[1,11]
1116no: 3+2=5[7,11]
7119sí: 4+3=7[7,9]
798no: 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
lohimedio (hacia arriba)resultadointervalo siguiente
084sí[4,8]
486sí[6,8]
687sí[7,8]
788no[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:

  1. 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.
  2. 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.

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.

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):

#ProblemaFaseQué practica
1Teletransportador cuánticoClasificatoria 2017ampliación: costo convexo; requiere justificar otra condición de búsqueda
2La leyenda de Zolda IINacional 2017binaria sobre el radio contando puntos

Más aplicaciones (en inglés)

#ProblemaDificultadQué practica
1K-divisible Sum (1476A)★★ (1000)el mínimo factible (¿hace falta la binaria?)
2Building an Aquarium (1873E)★★ (1100)binaria sobre la altura del agua
3Factory Machines (CSES 1620)★★★ (—)LA clásica de este módulo (la de la lección)
4Array 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»?


← 11 - Colas de prioridad · Ruta de Aprendizaje · 13 - Backtracking →