Почему это работает
- Большему кораблю никогда не нужно больше дней. Поэтому по грузоподъёмностям проверки «успеваем?» идут «нет, …, нет, да, …, да», а ответ — первое «да».
- Грузоподъёмность не меньше самой тяжёлой посылки, иначе та никогда не уедет, и не больше общего веса, при котором всё уезжает за день. Поэтому lo начинается с max(weights), а не с 1.
- Чтобы проверить одну грузоподъёмность, грузим посылки по порядку и начинаем новый день, только когда следующая не влезает. Если заполнять каждый день до предела, дней никогда не понадобится больше, чем при любой другой раскладке.
Сложность
Время O(n log s), где n — число посылок, а s — их общий вес: пробуем около log s грузоподъёмностей, и каждая проверка проходит по всем посылкам. Память O(1).
дальшеТеперь реши её сам, без подсказок.
Решить на LeetCode ↗