Бинпоиск по ответу

Условие

Есть посылки весом w[i], их нужно отправить по порядку за d дней. Каждый день грузим посылки подряд, пока суммарный вес не превысит вместимость машины. Найти минимальную вместимость.

Идея

Если вместимости c хватает, хватит и любой большей — свойство монотонно. Значит, ответ можно искать бинпоиском между max(w) и sum(w), а для каждого кандидата жадно проверять, укладываемся ли в d дней.

def days_needed(w, c):
    days, load = 1, 0
    for x in w:
        if load + x > c:
            days, load = days + 1, 0
        load += x
    return days

def min_capacity(w, d):
    lo, hi = max(w), sum(w)
    while lo < hi:
        mid = (lo + hi) // 2
        if days_needed(w, mid) <= d:
            hi = mid
        else:
            lo = mid + 1
    return lo

Время O(n · log S), где S — суммарный вес.