Проверяем гипотезу о пороге

В этой практике сначала сравнивайте гипотезы, а не вспоминайте каталог шаблонов. Все три условия ниже намеренно говорят о разных предметах. До разбора запишите для каждого: медленный эталон, величину-кандидат, быструю проверку, альтернативу и ожидаемую сложность.

Три задания, в которых ответ ещё не назван

Карточка A

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

Карточка B

Фильм разбит на кадры в заданном порядке. Его надо разрезать не более чем на K непрерывных роликов так, чтобы самый тяжёлый ролик был как можно легче. Каждый кадр должен попасть ровно в один ролик.

Карточка C

На линии стоят дома. Нужно выбрать минимальную дальность сигнала, чтобы M передатчиков покрыли все дома. Можно ли для выбранной дальности проверить осуществимость без перебора всех наборов позиций?

Для каждой карточки заранее ответьте: что произойдёт, если кандидат увеличить на единицу; какое утверждение станет односторонним; какая альтернатива не использует это свойство.

Раскрытие медленных ориентиров

Раскрытие A — после записи ответа

Можно проверить все допустимые грузоподъёмности от самого тяжёлого веса до суммы весов. Для каждой симулировать дни. Это корректно, но диапазон значений может быть огромным: при весах порядка миллиарда перебор каждой ёмкости неприемлем.

Раскрытие B — после записи ответа

Можно перечислять все K-1 границ разрезов. Это быстро становится комбинаторным перебором. Местоположение разрезов важно, но вопрос «разрешён ли предел L?» проще исходного вопроса об оптимуме.

Раскрытие C — после записи ответа

Вариант с перечислением мест передатчиков может быть экспоненциальным. Полезнее сначала проверить одну предполагаемую дальность и только затем выбирать, в какую сторону менять её.

Почему нельзя заново проверять каждый возможный ответ

В A жадная симуляция одного кандидата уже линейна по числу посылок. Повторять её для каждой ёмкости — это узкое место. Нужно использовать порядок кандидатов: если корабль справляется с ёмкостью 10, он справится и с 11; если не справляется с 10, не справится и с 9.

Раскрытие A: проверка, которая меняется только один раз

Для фиксированной грузоподъёмности достаточно идти по весам и заполнять текущий день до тех пор, пока следующая посылка помещается. Если получается не больше D дней, кандидат допустим. Увеличение ёмкости не может сделать расписание хуже, поэтому допустимые значения образуют суффикс диапазона.

Теперь имя подхода имеет смысл: это двоичный поиск по ответу, а не поиск элемента в отсортированном массиве. Мы ищем первую ёмкость, для которой проверка стала истинной.

Что доказывают границы поиска

Для непустого входа lower равен максимальному весу: меньшая ёмкость не перевезёт хотя бы одну посылку. Upper равен сумме: с такой ёмкостью все посылки поместятся за один день. Во время поиска все значения меньше lower уже доказанно недопустимы, а в отрезке [lower, upper] лежит минимальный допустимый ответ.

После проверки middle: если он допустим, ответ не больше middle и верхнюю границу можно сдвинуть; иначе ответ строго больше middle и сдвигается нижняя граница.

Как найти первый рабочий предел

1. Отвергните отрицательные веса и число дней меньше единицы.
2. Для пустого списка верните 0 по явно выбранному контракту.
3. Возьмите lower как максимальный вес, upper как сумму.
4. Пока lower < upper, проверьте среднее значение.
5. При успехе оставьте левую половину с middle; при неуспехе отбросьте middle и всё левее.
6. Когда границы совпадут, это минимальная допустимая грузоподъёмность.

Код после проверки гипотезы

Функция проверки не переставляет посылки: именно исходный порядок делает жадное заполнение дня корректным для данного контракта. C++ и Python одинаково считают дни и имеют одинаковое поведение на пустом и недопустимом входе.

C++17

#include <algorithm>
#include <cassert>
#include <iostream>
#include <stdexcept>
#include <vector>

using namespace std;

bool canShipWithinDays(const vector<int>& weights, int days, long long capacity) {
    int usedDays = 1;
    long long load = 0;

    for (int weight : weights) {
        if (load + weight > capacity) {
            ++usedDays;
            load = 0;
        }
        load += weight;
    }
    return usedDays <= days;
}

long long minimumShipCapacity(const vector<int>& weights, int days) {
    if (days <= 0) throw invalid_argument("days must be positive");
    if (weights.empty()) return 0;

    long long lower = 0;
    long long upper = 0;
    for (int weight : weights) {
        if (weight < 0) throw invalid_argument("weights must be non-negative");
        lower = max(lower, static_cast<long long>(weight));
        upper += weight;
    }

    while (lower < upper) {
        long long middle = lower + (upper - lower) / 2;
        if (canShipWithinDays(weights, days, middle)) {
            upper = middle;
        } else {
            lower = middle + 1;
        }
    }
    return lower;
}

int main() {
    assert(minimumShipCapacity({1, 2, 3, 1, 1}, 4) == 3);
    assert(minimumShipCapacity({3, 2, 2, 4, 1, 4}, 3) == 6);
    assert(minimumShipCapacity({}, 3) == 0);
    bool rejected = false;
    try {
        minimumShipCapacity({1, 2}, 0);
    } catch (const invalid_argument&) {
        rejected = true;
    }
    assert(rejected);
    cout << "ok\n";
}

Python 3

def can_ship_within_days(weights: list[int], days: int, capacity: int) -> bool:
    used_days = 1
    load = 0

    for weight in weights:
        if load + weight > capacity:
            used_days += 1
            load = 0
        load += weight

    return used_days <= days


def minimum_ship_capacity(weights: list[int], days: int) -> int:
    if days <= 0:
        raise ValueError("days must be positive")
    if not weights:
        return 0
    if any(weight < 0 for weight in weights):
        raise ValueError("weights must be non-negative")

    lower = max(weights)
    upper = sum(weights)
    while lower < upper:
        middle = lower + (upper - lower) // 2
        if can_ship_within_days(weights, days, middle):
            upper = middle
        else:
            lower = middle + 1
    return lower


assert minimum_ship_capacity([1, 2, 3, 1, 1], 4) == 3
assert minimum_ship_capacity([3, 2, 2, 4, 1, 4], 3) == 6
assert minimum_ship_capacity([], 3) == 0
try:
    minimum_ship_capacity([1, 2], 0)
    assert False, "non-positive days must be rejected"
except ValueError:
    pass
print("ok")

Сколько стоит проверка каждого порога

Пусть S — сумма весов. Одна проверка проходит по массиву за O(n) времени и O(1) памяти; двоичный поиск делает O(log S) проверок. Итого O(n log S) времени и O(1) дополнительной памяти. Это не O(log n): двоичный поиск идёт по диапазону возможных ответов, а не по позициям массива.

Какие условия меняют контракт

• Если D больше числа посылок, ответ всё равно не меньше максимального веса.
• Один тяжёлый вес задаёт нижнюю границу.
• Пустой список возвращает 0 только потому, что это явно выбрано в API.
• Нулевая или отрицательная ёмкость не является допустимым ответом для положительных весов.
• Отрицательные веса нарушают модель заполнения корабля и отвергаются, а не «поддерживаются случайно».

Четыре упражнения для отладки решения

Отладка

Замените условие переполнения на load + weight >= capacity. На весах [1,2,3,1,1], D = 4 и capacity = 3 ровно заполненный день ошибочно станет двумя днями. Проверьте, что равенство разрешено.

Границы

Прогоните пустой список, одну посылку, D = 1, D > n, нулевой D и отрицательный вес. Для каждого случая скажите, это допустимый результат или ошибка контракта.

Сложность

Объясните, почему один вызов canShipWithinDays не содержит вложенного перебора: указатель по весам никогда не возвращается назад.

Объяснение вслух

За минуту скажите интервьюеру: «Я умею проверить фиксированную ёмкость линейно. Если она работает, любая большая тоже работает, поэтому ищу первую работающую границу». Затем назовите начальные lower и upper.

Когда ответ сам становится пространством поиска

Сигналы: «минимизировать максимальное», «максимизировать минимальное», целый ответ лежит в диапазоне и для одного кандидата есть быстрая проверка, которая не меняет истинность обратно при движении в одну сторону. Перед выбором метода всегда сформулируйте эту проверку словами.

Когда односторонней проверки нет

Не используйте такой поиск, если допустимость кандидата то появляется, то исчезает, или если вы не умеете проверить её быстрее полного оптимизационного перебора. При вещественном ответе нужна оговорённая точность и другой критерий остановки. Если порядок посылок можно менять, меняется сама проверка и доказательство жадного заполнения.

Самопроверка: почему верхняя граница существует

Вопрос: почему сумма всех весов — допустимая верхняя граница?
Ответ: все неотрицательные посылки можно погрузить в один день, а один день не превышает любое положительное D. Поэтому проверка для этой ёмкости истинна.

Самопроверка: другая сложность

Вопрос: почему перебор ёмкостей от maxWeight до sumWeights может быть хуже O(n²)?
Ответ: число кандидатов зависит от величин весов, а не только от их количества. Две посылки весом миллиард уже дают огромный диапазон.

Решаем смешанный сет с отложенным раскрытием

Решите задачу о разбиении массива неотрицательных чисел на не более K непрерывных частей с минимально возможной максимальной суммой части. Сначала запишите свою проверку кандидата. Затем сверяйтесь: при фиксированном пределе жадно начинайте новую часть только тогда, когда следующий элемент уже не помещается.

Два новых условия без названного паттерна

Без подсказок выберите состояние, медленный эталон, альтернативу и оценку. Не смотрите разборы до собственной попытки.

Задача 1

Дана позиция коров на прямой и число M. Найдите наибольшее минимальное расстояние между любыми двумя выбранными коровами. Координаты неотрицательные, M не превышает числа позиций.

Задача 2

Дан массив положительных книг и число K. Разделите книги между не более чем K переписчиками, сохраняя порядок, чтобы максимальное число страниц у одного было минимальным. Верните этот минимум.

Что должно остаться после этой диагностики

Название «двоичный поиск» не оправдывает решение. Его оправдывают четыре фразы: кандидат ответа, проверка кандидата, односторонность проверки и инвариант границ. Если хотя бы одну из них нельзя сказать вслух, сначала вернитесь к медленному эталону.