¿Cuáles son algunos buenos acertijos de programación que usan una búsqueda binaria?

Answer 1

Permíteme contarte un truco que se usa con mucha frecuencia en los Concursos de codificación competitiva que generalmente implica una búsqueda binaria modificada. La declaración del problema es la siguiente:
POLVO MÁGICO
La primera línea contiene dos enteros positivos n y k : la cantidad de ingredientes y la cantidad de gramos del polvo mágico.

La segunda línea contiene la secuencia a 1, a 2, …, donde el i -ésimo número es igual a la cantidad de gramos del i -ésimo ingrediente, necesario para hornear una galleta.

La tercera línea contiene la secuencia b 1, b 2, …, bn , donde el número i es el número de gramos del ingrediente i , que tiene Apollinaria.

Imprima la cantidad máxima de galletas que Apollinaria podrá hornear utilizando los ingredientes que tiene y el polvo mágico.

Descripción detallada aquí

Solución:

Vamos a comprobar que la respuesta actual es igual a cur . Entonces la función objetivo debe realizarse de la siguiente manera. Guardemos en la variable cnt cuántos gramos de polvo mágico necesitamos para hornear galletas cur . Recorramos los ingredientes y el ingrediente actual tiene el número i . Entonces, si a [ i ] · cur > b [ i ] hagamos cnt = cnt + a [ i ] · cur – b [ i ]. Si después de mirar algún ingrediente cnt se vuelve más de k, la función objetivo debe devolver falso . Si no existe tal ingrediente, la función objetivo debe ser verdadera .

Si la función objetivo devuelve verdadero , necesitamos mover el extremo izquierdo de la búsqueda binaria al cur , de lo contrario, debemos mover el extremo derecho de la búsqueda binaria al cur .

Mi solución cpp:
POLVO MÁGICO – enfoque de búsqueda binaria