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

110. Вместимость машины до ПВЗ

Сложная

Коробки для пункта выдачи Wildberries стоят на рампе в порядке boxes — вес каждой в килограммах. Грузят строго по очереди: машина берёт несколько коробок подряд, пока суммарный вес не превышает вместимость, и уезжает.

Нужно увезти все коробки не больше чем за trips рейсов. Найдите наименьшую вместимость машины, при которой это возможно.

Коробку делить нельзя, переставлять тоже.

В работе: Выбор класса машины для ночного рейса на ПВЗ: брать «газель» на 1,5 т или хватит каблука на 700 кг.

Пример 1

Ввод
boxes = [120, 80, 300, 40, 60, 200]
trips = 3
Вывод
300

Вместимость 300: [120, 80] [300] [40, 60, 200]. На 299 не влезет коробка 300.

Пример 2

Ввод
boxes = [50, 50, 50]
trips = 1
Вывод
150

Один рейс — машина должна взять всё: 150.

Ограничения

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

Источник: наша задача на данных Wildberries. Условие пересказано своими словами.