Capacity To Ship Packages Within D Days

Средняя№1011поиск по ответу

Посылки с заданными весами нужно отправить по порядку за заданное число дней. Каждый день корабль берёт следующие посылки из очереди, пока их общий вес не превышает его грузоподъёмность. Нужно найти наименьшую грузоподъёмность, при которой всё уедет вовремя. Наш пример: веса [3, 2, 2, 4, 1, 4], 3 дня — ответ 6: [3, 2], [2, 4], [1, 4].

1011 Capacity To Ship Packages Within D DaysРазбор · 1×

Пример: Веса [3, 2, 2, 4, 1, 4], 3 дня. Верхний ряд — грузоподъёмности 4..16; ниже посылки, сгруппированные по дню отправки при грузоподъёмности mid.

грузоподъёмность45678910111213141516loпосылки322414дни—
грузоподъёмность ещё возможнапроверяемпогружена в свой деньотброшенаответ

Самая тяжёлая посылка, 4, должна влезть в один день: lo = 4

01/56
сначала · назад · пуск · шаг
Скорость
1function shipWithinDays(weights, days):
2 lo = max(weights) // the heaviest has to fit
3 hi = sum(weights) // everything in one day
4 while lo < hi:
5 mid = floor((lo + hi) / 2)
6 need = 1; load = 0
7 for each w in weights:
8 if load + w > mid: need = need + 1; load = 0
9 load = load + w
10 if need <= days:
11 hi = mid // in time: keep mid
12 else:
13 lo = mid + 1
14 return lo
состояние
lo
4
hi
–
mid
–
need
–
load
–
историянажмите шаг, чтобы вернуться

← → шаг · пробел — пауза

Почему это работает

  1. Большему кораблю никогда не нужно больше дней. Поэтому по грузоподъёмностям проверки «успеваем?» идут «нет, …, нет, да, …, да», а ответ — первое «да».
  2. Грузоподъёмность не меньше самой тяжёлой посылки, иначе та никогда не уедет, и не больше общего веса, при котором всё уезжает за день. Поэтому lo начинается с max(weights), а не с 1.
  3. Чтобы проверить одну грузоподъёмность, грузим посылки по порядку и начинаем новый день, только когда следующая не влезает. Если заполнять каждый день до предела, дней никогда не понадобится больше, чем при любой другой раскладке.

Сложность

Время O(n log s), где n — число посылок, а s — их общий вес: пробуем около log s грузоподъёмностей, и каждая проверка проходит по всем посылкам. Память O(1).

дальшеТеперь реши её сам, без подсказок.

Решить на LeetCode ↗

Задача и её условие принадлежат LeetCode. Здесь — наш пересказ, наш пример и наше решение. Patterns Hero не связан с LeetCode.