Book Allocation Problem
На полке книги расположены в фиксированном порядке, а pages[i] — количество страниц в книге i. Распределите книги между students учениками: каждый ученик получает один непрерывный ряд соседних книг, не менее одной книги, и каждая книга достаётся ровно одному ученику. Нагрузка ученика — это общее количество страниц в полученных им книгах.
Верните наименьшее возможное значение наибольшей нагрузки. Если учеников больше, чем книг, верните -1.
Функция
- pagesinteger-array
- количество страниц каждой книги в порядке расположения на полке
- studentsinteger
- количество учеников, которые делят книги
- Возвращаетinteger
- минимально возможная максимальная нагрузка или -1, если учеников больше, чем книг
Ограничения
1 ≤ pages.length ≤ 50001 ≤ pages[i] ≤ 1051 ≤ students ≤ 104- Верни
-1, еслиstudents > pages.length.
Примеры
- Ввод
- pages = [25, 40, 15, 30, 50]students = 3
- Вывод
- 65
- Пояснение
- Раздайте
[25, 40],[15, 30]и[50]: нагрузки составляют 65, 45 и 50. Ограничение в 64 не подходит: при раздаче получаются[25],[40, 15],[30],[50]— четыре ученика.
- Ввод
- pages = [10, 20]students = 3
- Вывод
- -1
- Пояснение
- Двух книг не хватит, чтобы выдать каждому из трёх учеников по одной книге, поэтому ответ —
-1.
- Ввод
- pages = [7, 3, 9]students = 3
- Вывод
- 9
- Пояснение
- Три книги и три ученика: каждому ученику достаётся по одной книге. Самая тяжёлая — книга на 9 страниц.
Дополнительный вопрос
Докажите, что средняя доля, округлённая вверх, плюс самая толстая книга всегда является рабочей верхней границей. Сколько проверок позволяет сэкономить эта верхняя граница на полке с тонкими книгами?
Подсказки
Открывайте по одной. Каждая подсказывает чуть больше.
Вместо того чтобы искать оптимальные варианты разрезания, выберите ограничение на количество страниц. Сколько учеников вам понадобится, если никому нельзя нести больше этого количества?
Раздавайте книги по порядку на полке и переходите к следующему ученику только тогда, когда следующая книга превысит лимит. Более высокий лимит никогда не требует больше учеников.
Верни
-1, если учеников больше, чем книг. В противном случае найди предел бинарным поиском в диапазоне от большего из количества страниц в самой толстой книге и средней доли до общего количества.
Решение
Есть слишком много способов разделить книги на полке, но проверить один лимит страниц несложно: раздавайте книги в порядке на полке, переходя к следующему ученику, когда следующая книга превысит лимит, и подсчитайте количество учеников. При более высоком лимите учеников никогда не потребуется больше, поэтому подходящие лимиты образуют непрерывный диапазон, а двоичный поиск находит его начало.
Увеличивайте лимит страниц на одну страницу за раз
Верно, но не успевает на самых больших тестах
Идея
Начни с L = max(pages), поскольку кому-то достаётся самая толстая книга, и увеличивай L на одну страницу за раз, пока жадный подсчёт не уложится в students. Все меньшие пределы не подошли, поэтому первый подходящий и есть ответ. В первом примере для каждого предела от 50 до 64 нужны четыре студента, а для 65 — три: 16 проверок.
Ответом может быть вся полка: один студент и 5000 книг по 10^5 страниц означают около 5 × 10^8 пределов, для каждого из которых нужно пройти по всем 5000 книгам. В столбце времени A — это ответ, а m — самая толстая книга.
Алгоритм
- Если
students > pages.length, верните-1. - Опишите жадный подсчёт для ограничения
L: начните с одного студента и нагрузки 0; когдаload + pages[i] > L, добавьте студента и установите нагрузку равнойpages[i], иначе добавьте книгу к нагрузке. - Установите
Lравным самой толстой книге. - Пока количество для
Lбольше, чемstudents, увеличивайтеLна 1. - Верните
L.
def studentsNeeded(pages, limit):
count, load = 1, 0 # the first student starts with no pages
for p in pages:
if load + p > limit:
count += 1 # this book opens the next student's block
load = p
else:
load += p
return count
def allocateBooks(pages, students):
if students > len(pages):
return -1 # someone would get no book
limit = max(pages) # the thickest book has to fit somewhere
while studentsNeeded(pages, limit) > students:
limit += 1
return limitДвоичный поиск при ограничении на количество страниц
Идея
Жадное количество — это наименьшее число учеников, которое может потребоваться при любом распределении книг при L. Если сравнивать учеников по одному с учениками при любом другом распределении, каждый ученик при жадном распределении останавливается только тогда, когда следующая книга уже не помещается, поэтому он заканчивает как минимум не раньше на полке. Если учеников меньше, чем у тебя есть, это нормально: ученик, у которого две книги, может передать одну ученику, у которого нет ни одной, и ни одна нагрузка не увеличится.
Значит, L подходит в точности тогда, когда жадное количество не превышает students. Любое распределение, которое подходит при L, подходит и при L+1, поэтому бинарный поиск находит наименьшее подходящее ограничение.
Диапазон начинается с большего из значений max(pages) и средней доли, то есть total / students, округлённой вверх, поскольку самая большая нагрузка не меньше обоих значений. Верхняя граница — total. В первом примере это диапазон от 54 до 160, и поиск проверяет 107, 80, 67, 60, 64, 66 и 65.
Алгоритм
- Если
students > pages.length, верните-1. - Сложите значения
totalи найдите самую толстую книгу. Установитеloравным большему из значений: самой толстой книге и(total + students - 1) / students, аhi = total. - Пока
lo < hi, вычисляйтеmid = lo + (hi - lo) / 2. - Выполните жадный подсчёт для
mid. Если результат не превышаетstudents, установитеhi = mid; иначе установитеlo = mid + 1. - Верните
lo.
def studentsNeeded(pages, limit):
count, load = 1, 0 # the first student starts with no pages
for p in pages:
if load + p > limit:
count += 1 # this book opens the next student's block
load = p
else:
load += p
return count
def allocateBooks(pages, students):
if students > len(pages):
return -1 # someone would get no book
total = sum(pages)
# no limit can be below the thickest book or below the average share
lo = max(max(pages), (total + students - 1) // students)
hi = total # one student could carry the whole shelf
while lo < hi:
mid = lo + (hi - lo) // 2
if studentsNeeded(pages, mid) <= students:
hi = mid # mid is enough, so the answer is mid or lower
else:
lo = mid + 1 # mid needs too many students
return lo
Ловушки и крайние случаи
- Пропуск проверки
-1. Для[10, 20]и 3 студентов жадный подсчёт при ограничении 20 равен 2, поэтому поиск возвращает 20. - Начало диапазона только со средней доли. Для
[1, 9]и 2 студентов среднее равно 5, и при таком ограничении жадный алгоритм оставляет книгу на 9 страниц отдельно, насчитывает 2 и возвращает 5. - Проверка на точное равенство
students. Для[5, 5, 5, 5, 5, 5]и 4 студентов ответ равен 10, при этом жадный подсчёт равен 3. - Сортировка книг. Для
[10, 1, 1, 10]и 2 студентов результат равен 11, но после сортировки в[1, 1, 10, 10]он равен 12.
Частые вопросы3
Задача о распределении книг — это то же самое, что и задача о разбиении массива с максимальной суммой?
Да. Оба варианта разбивают массив на фиксированное число непустых смежных блоков и минимизируют сумму наибольшего блока, и для обоих подходит один и тот же двоичный поиск с той же жадной проверкой. В версии из книги добавлен случай -1.
Какова временная сложность задачи распределения книг?
Время O(n log S) и дополнительная память O(1), где n — количество книг, а S — общее количество страниц. Для каждой проверяемой границы требуется один проход по книгам, а поиск проверяет примерно log2 S границ: 29 для полки с 5 × 10^8 страницами.
Когда невозможно распределить книги?
Только если учеников больше, чем книг, поскольку каждому ученику нужна как минимум одна книга. Если книг достаточно, любой блок из двух или более книг может отдать последнюю книгу ученику, у которого её нет, пока у каждого не будет по одной.
Похожие задачи
Задачи на те же идеи. Решите две или три, и приём запомнится.
def allocateBooks(pages, students):
# Напишите код здесьТест #1
Тест #2
Тест #3
Аргументы
pages = [25, 40, 15, 30, 50] students = 3
Ожидаемый вывод
65