Минимальное время, оставшееся до срабатывания аварийной сигнализации

Опубликовано: 21 Сентября, 2022

Компьютерщик организует велогонку с N байкерами. Начальная скорость i -го байкера обозначается H i км/ч , а ускорение i -го байкера — A i км/ч 2 . Байкер, чья скорость равна «L» или выше, считается быстрым байкером. Общая скорость на трассе за каждый час рассчитывается путем сложения скорости каждого быстрого байкера в этот час. Когда общая скорость на трассе составляет «М» километров в час и более, включается аварийная сигнализация. Задача состоит в том, чтобы найти минимальное количество часов, через которое сработает охранная сигнализация.

Примеры:

Input: N = 3, M = 400, L = 120, H = {20, 50, 20}, A = {20, 70, 90}
Output: 3
Explanation:
Speeds of all the Bikers at ith hour:
Biker1 = [20  40  60  80 100]
Biker2 = [50 120 190 260 330]
Biker3 = [20 110 200 290 380].

Initial Speed on track  = 0, because none of the biker’s speed is fast enough.
Speed on track after 1st Hour = 120.
Speed on track after 2nd Hour = 190 + 200 = 390.
Speed on track after 3rd Hour = 260 + 290.
Alarm will start at the 3rd hour.

Input: N = 2, M = 60, L = 120, H = {50, 30}, A = {20, 40}
Output: 3

Подход: Данную задачу можно решить с помощью бинарного поиска, используя тот факт, что если велосипеды имеют начальную скорость U и равномерное ускорение A , то скорость в любой момент времени можно найти с помощью уравнения: (V = U + A*t) , и если в момент времени t условия удовлетворяются, то для всего времени, превышающего t , будут удовлетворяться, поэтому отбрасываем правую половину диапазона, пока не будет найдено минимальное значение. Выполните следующие шаги, чтобы решить проблему:

  • Определите проверку функции (long H[], long A[], long mid, long N, long M, long L) и выполните следующие шаги:
    • Инициализируйте переменную, скажем, sum как 0 , которая хранит сумму скоростей.
    • Перебрать диапазон [0, N], используя переменную i , и если значение (mid*A[i] + H[i]) не меньше L , то добавить это значение к сумме .
    • После выполнения вышеперечисленных действий вернуть в качестве результата значение суммы .
  • Инициализируйте переменные, скажем, 0 и 10 10 в качестве диапазона двоичного поиска ответа и 0 , который хранит минимальное количество часов.
  • Повторяйте до low <= high и выполняйте следующие шаги:
    • Найдите значение mid как (low + high)/2 .
    • Вызовите функцию check(H, A, mid, N, M, L) и, если значение, возвращаемое функцией, не меньше M , обновите значение ans как mid . В противном случае обновите значение high как (mid – 1) .
    • В противном случае обновите значение low как (mid + 1) .
  • После выполнения вышеуказанных шагов выведите значение ans как результирующее количество часов.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N*log(max(L, M)))
Вспомогательное пространство: O(1)

РЕКОМЕНДУЕМЫЕ СТАТЬИ