Войти Регистрация
Алгоритмы

190. Вместимость кейса инкассатора

Средняя

В cash[i] — сколько тысяч рублей нужно забрать из i-го банкомата Альфа‑Банка. Один рейс увозит из одного банкомата не больше cap тысяч, поэтому на банкомат уходит ⌈cash[i] / cap⌉ рейсов.

За смену бригада делает не больше trips рейсов. Верните наименьшую целую вместимость cap, при которой хватит смены. Гарантируется, что trips ≥ n.

В работе: Банк выбирает модель кейса для района из 600 банкоматов и 900 рейсов в смену: кейсы на 2000 и на 5000 тысяч отличаются по цене страховки, и брать больший без расчёта дорого.

Пример 1

Ввод
cash = [3000, 1200, 4500, 800]
trips = 6
Вывод
2250

При cap = 2250: 2 + 1 + 2 + 1 = 6 рейсов; при 2249 нужно уже 7.

Пример 2

Ввод
cash = [500]
trips = 1
Вывод
500

Один рейс — кейс на всю сумму.

Ограничения

  • 1 ≤ n ≤ 10⁵
  • 1 ≤ cash[i] ≤ 10⁹
  • n ≤ trips ≤ 10⁹
  • Лимит — 2 с на тест (2000 мс).
Как вызывается ваш код Читать ввод и печатать ответ не нужно: мы вызываем функцию на каждом тесте и сравниваем то, что она вернула. print() и console.log() уходят в консоль. 
def min_case_capacity(cash, trips):
Бинарный поиск по ответуцельO(n log n)

Источник: наша задача на данных Альфа-Банка. Условие пересказано своими словами.