Двоичный поиск кажется довольно интуитивным и простым. Давайте перефразируем вопрос:
Учитывая время t
, вычислим максимальное количество поездок, которое можно предпринять.
Мы можем сделать это в O(K)
. Учтите, что каждая кабина i
может совершить до t / k_i
поездок за t
время, и мы можем просто получить сумму всех t / k_i
для каждого i
, чтобы получить максимальное количество поездок, совершенных в t
время. Это позволяет нам построить функцию, по которой мы можем выполнить бинарный поиск:
def f(time):
n_trips = 0
for trip_time in cabs:
n_trips += time // trip_time
return n_trips
Очевидно, из этого следует, что с увеличением количества времени количество поездок, которое мы можем совершить, также будет увеличиваться, поэтому f(x)
не-снижение, что означает, что мы можем запустить бинарный поиск по нему.
Мы выполняем двоичный поиск минимума t
, который дает N
или более отключений в качестве вывода, и это можно сделать в O(KlogW)
, где W
- это диапазон всех t
, которые мыдолжен рассмотреть.