Чтецы аудиокниги
Студия записывает аудиокнигу «Войны и мира». Главы одной части раздают k чтецам; каждую главу целиком читает кто-то один, все чтецы работают одновременно, и часть готова, когда закончит самый занятой. Длительность каждой главы известна в минутах — в тестах это настоящие главы романа при чтении 150 слов в минуту. Как раздать главы, чтобы часть была готова как можно раньше?
Вход
В первой строке число глав n и число чтецов k (1 ≤ n ≤ 20, 1 ≤ k ≤ 6). Во второй — n длительностей глав в минутах, целые от 1 до 60.
Выход
Наименьшее возможное время работы самого занятого чтеца, в минутах.
Примеры
Пример 1
5 2 3 3 2 2 2
6
Ограничения
- Время · Python
- 5000 мс
- Время · Go
- 1500 мс
- Память
- 256 МБ
- Проверка
- 14 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Самое естественное: брать главы по убыванию длины и отдавать каждую тому, кто сейчас свободнее всех. Проверьте на примере: главы 3, 3, 2, 2, 2 и два чтеца.
2Подсказка 2
Точный ответ даёт перебор: каждую главу по очереди отдаём каждому чтецу. Это kn вариантов — для 20 глав и четырёх чтецов около триллиона. Какие ветки дерева перебора можно не открывать, ничего не потеряв?
3Идея
Перебор с отсечениями из статьи, все сразу. Рекорд — лучший найденный ответ, и с самого начала это ответ жадного способа из первой подсказки. Отсекаем ветку, если кто-то из чтецов уже не меньше рекорда; если двум чтецам с одинаковой нагрузкой предлагаем одну и ту же главу — пробуем только первого; если оставшиеся главы не помещаются в «запас» чтецов (каждый может взять ещё не больше рекорд − 1 − нагрузка); и останавливаемся совсем, как только рекорд сравнялся с нижней оценкой max(самая длинная глава, ⌈сумма / k⌉). Главы раздаём от длинных к коротким.
4Разбор
Почему жадный способ ошибается на примере. Он отдаёт тройки разным чтецам, а потом три двойки — 3 + 2 + 2 = 7 и 3 + 2 = 5. Лучше 3 + 3 = 6 и 2 + 2 + 2 = 6: две тройки вместе, хотя каждая по отдельности «должна» идти к свободному. Жадность смотрит на один шаг и не видит, что тройкам выгодно собраться вместе. Рональд Грэм доказал в 1969 году, что такой жадный способ ошибается не больше чем в 4/3 раза, но ошибается — на восьми тестах из четырнадцати.
Каждое отсечение безопасно, то есть не выбрасывает ветку, где есть ответ лучше рекорда: в ветке, где чтец уже не меньше рекорда, все раскладки не лучше рекорда; два чтеца с равной нагрузкой взаимозаменяемы, и ветка второго — зеркальная копия ветки первого; если запаса меньше, чем осталось глав, лучше рекорда раздать их нельзя; а нижнюю оценку не побить никакой раскладкой. Подробное доказательство — в разделе статьи «Почему ничего не теряется».
На настоящих главах этого хватает с огромным запасом: самому долгому тесту эталону на Python нужно меньше сотой доли секунды. Но гарантий нет: бывают входы, где тот же перебор идёт миллионы узлов, — замер в статье показывает такие всплески.
4+Решение
5Сложность
В худшем случае — O(kn), как у любого перебора: задача трудная (к ней сводится разбиение чисел на две равные кучи). На деле — тысячи узлов, иногда единицы.
6Типичные ошибки
- Жадность. Ошибается на примере и ещё на семи тестах — где на минуту, где на три.
- Перебор без отсечений. Верен, но 420 ≈ 1012 узлов не укладываются во время.
- Отсечь «больше среднего». Отсекать ветку, где кто-то читает больше ⌈сумма / k⌉, нельзя: среднее — нижняя оценка, но её не всегда можно достичь, и тогда такое отсечение выбросит все решения. В большинстве тестов это сошло бы с рук, но в двух последних нижней оценки достичь нельзя: три главы по полчаса на двоих никак не разделить по 45 минут.
- Остановка при «хорошем» ответе. Останавливаться можно только на нижней оценке, а не когда ответ «перестал улучшаться»: улучшение может прийти в последней ветке.