5811. Минимальная грузоподъёмность фургона
Medium
0 решили
Коробки стоят в ряд, их веса заданы массивом
Грузоподъёмность — наибольший суммарный вес, который фургон берёт за одну ходку. Найдите минимальную грузоподъёмность, при которой все коробки уедут не больше чем за
Одну коробку нельзя делить между ходками, поэтому ответ не меньше самой тяжёлой коробки. Если ходка одна, ответ равен сумме всех весов.
weights. Фургон увозит их не более чем за days ходок. За одну ходку он забирает несколько подряд идущих коробок с начала оставшегося ряда и не возвращается за пропущенными: порядок сохраняется, ряд делится на отрезки.Грузоподъёмность — наибольший суммарный вес, который фургон берёт за одну ходку. Найдите минимальную грузоподъёмность, при которой все коробки уедут не больше чем за
days ходок. Ходок можно сделать меньше, чем days. Пустая ходка не нужна.Одну коробку нельзя делить между ходками, поэтому ответ не меньше самой тяжёлой коробки. Если ходка одна, ответ равен сумме всех весов.
Примеры:
Вход:
weights = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], days = 5
Выход:
15
Объяснение: Пять ходок: 1+2+3+4+5, 6+7, 8, 9, 10. Самая тяжёлая весит 15. При 14 шестая ходка уже нужна.
Вход:
weights = [3, 2, 2, 4, 1, 4], days = 3
Выход:
6
Объяснение: Например, 3+2, 2+4 и 1+4. При грузоподъёмности 5 нужны уже четыре ходки.
Вход:
weights = [1, 2, 3, 1, 1], days = 4
Выход:
3
Объяснение: Коробка весом 3 не режется, меньше трёх фургон быть не может. Четырёх ходок при этом хватает.
Ограничения:
1 <= weights.length <= 10^5
1 <= weights[i] <= 10^4
1 <= days <= weights.length
Решите эту задачу в браузере
Создайте бесплатный аккаунт — редактор Python и Java, проверка на тестах за секунды.
Комментарии (0)
Зарегистрируйтесь или войдите, чтобы оставить комментарий
Пока нет комментариев. Будьте первым!