Бинарный поиск по ответу: задача о распределении книг

Зачем это читать?

Задача «Распределение книг» — классика собеседований в FAANG. Она учит применять бинарный поиск не к массиву, а к диапазону возможных ответов. Освоив этот паттерн, вы сможете решать десятки похожих задач: Aggressive Cows, Painter's Partition, Koko Eating Bananas и другие.

Постановка задачи

Даны массив books, где books[i] — количество страниц в i-й книге, и число m студентов. Нужно распределить книги так, чтобы:

• каждый студент получил хотя бы одну книгу;
• книги распределяются последовательно (подряд);
• каждая книга отдана ровно одному студенту;
• минимизировать максимальное количество страниц, доставшееся одному студенту.

Верните минимально возможное значение максимума страниц.

Брутфорс: перебор всех вариантов

На собеседовании можно начать с наивного подхода: перебрать все возможные лимиты страниц X от max(books) до sum(books) и проверить, можно ли распределить книги так, чтобы ни один студент не получил больше X страниц. Сложность O(N × Sum) — слишком медленно для больших сумм.

Оптимальный подход: бинарный поиск по ответу

Заметим, что ответ лежит в диапазоне от max(books) (самая толстая книга) до sum(books) (все книги у одного студента). Главная идея: мы не перебираем все значения, а используем бинарный поиск по этому диапазону. Для каждого среднего значения mid проверяем, возможно ли распределение с лимитом mid. Если да — пробуем уменьшить лимит, если нет — увеличиваем.

Ключевое свойство, делающее бинарный поиск возможным: если распределение возможно при лимите X, то оно возможно и при любом Y > X. Монотонность гарантирует корректность поиска.

Функция проверки (feasibility)

Проверка работает за O(N): мы последовательно выделяем книги студентам, пока не превысим лимит max_pages. Как только превышение — переходим к следующему студенту. Если количество студентов не превышает m — распределение возможно.

def is_possible(books, m, max_pages):
    students = 1
    pages = 0
    for book in books:
        if pages + book <= max_pages:
            pages += book
        else:
            students += 1
            pages = book
    return students <= m

Полное решение на Python

def allocate_books(books, m):
    if m > len(books):
        return -1  # студентов больше, чем книг — невозможно
    
    low = max(books)   # минимальный возможный ответ
    high = sum(books)  # максимальный возможный ответ
    
    while low < high:
        mid = (low + high) // 2
        if is_possible(books, m, mid):
            high = mid  # пробуем уменьшить лимит
        else:
            low = mid + 1  # увеличиваем лимит
    return low

Пример работы

Пусть books = [12, 34, 67, 90], m = 2.

• low = 90, high = 203
• mid = 146 → распределение: 12+34+67=113 (студент 1), 90 (студент 2) → 2 студента, возможно → high = 146
• mid = 118 → 12+34+67=113 (студент 1), 90 (студент 2) → 2 студента → high = 118
• mid = 104 → 12+34=46 (студент 1), 67 (студент 2), 90 (студент 3) → 3 студента > 2 → low = 105
• mid = 111 → 12+34+67=113 > 111 → 12+34=46 (студент 1), 67 (студент 2), 90 (студент 3) → 3 студента → low = 112
• mid = 115 → 12+34+67=113 (студент 1), 90 (студент 2) → 2 студента → high = 115
• mid = 113 → 12+34+67=113 (студент 1), 90 (студент 2) → 2 студента → high = 113
• low = 113, high = 113 → ответ 113

Сложность

• Время: O(N × log(Sum)) — N книг, бинарный поиск по сумме страниц
• Память: O(1) — только несколько переменных

Паттерн: когда применять бинарный поиск по ответу

Если в условии задачи есть фразы «минимизировать максимум» или «максимизировать минимум», и вы можете быстро проверить, возможен ли ответ, — используйте бинарный поиск по диапазону ответов. Этот паттерн встречается в задачах:

• Распределение книг
• Агрессивные коровы
• Разделение массива на подмассивы с минимальной суммой
• Доставка грузов за D дней
• Коко, поедающая бананы

Практический вывод

Прямо сейчас откройте LeetCode и решите задачу 1011. Capacity To Ship Packages Within D Days. Примените тот же шаблон: бинарный поиск по весу груза, функция проверки за O(N). Закрепите паттерн на трёх-четырёх задачах — и вы будете узнавать его в любой формулировке.

Запомните ментальную модель: «Могу ли я распределить, если максимум не превышает X?» Если да — уменьшаем X, если нет — увеличиваем. Бинарный поиск по ответу — ваш новый супер-инструмент.