Роман за k дней
Книга состоит из n глав, известна длина каждой в словах. Читать нужно по порядку и по целым главам, а прочитать книгу — за k дней (можно и быстрее). Какой наименьший предел слов в день это позволяет? Для каждого k из списка нужен свой ответ.
Второй и третий тесты — 361 глава «Войны и мира». За месяц нужно читать не больше 15 802 слов в день, а если растянуть на год, предел упирается в самую длинную главу.
Вход
В первой строке n и q (1 ≤ n ≤ 10⁵, 1 ≤ q ≤ 10). Во второй — длины глав, целые от 1 до 10⁶. В третьей — q чисел k (1 ≤ k ≤ 10⁹).
Выход
Для каждого k — наименьший дневной предел.
Примеры
Пример 1
6 4 5 2 7 3 4 6 1 2 3 6
27 14 10 7
Ограничения
- Время · Python
- 7000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 6 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Если предел L позволяет уложиться в k дней, то и любой предел больше L позволяет. А проверить конкретный предел легко: читать каждый день столько глав, сколько влезает.
2Идея
Ответ — первое L, для которого «дней нужно не больше k». Функция «сколько дней нужно при пределе L» не растёт с ростом L, поэтому граница ищется двоичным поиском по L, а каждый кандидат проверяется жадно за один проход.
3Разбор
Отрезок поиска: снизу — самая длинная глава (меньше нельзя: её не разорвать), сверху — сумма всех глав (вся книга за день). Жадная проверка права: класть главу в текущий день, пока помещается, — выгодно всегда, потому что любой план можно поправить так, чтобы ранние дни были заполнены не меньше, и дней от этого не прибавится.
Сумма доходит до 10¹¹ — в Go нужен int64.
3+Решение
4Сложность
Отрезок длиной до 10¹¹ — около 37 проверок, каждая O(n): O(n log S) на один k, где S — сумма длин.
5Типичные ошибки
- Перебор пределов подряд. От самой длинной главы до ответа бывает больше миллиона шагов, и каждый — проход по главам.
- Нижняя граница ноль. Предел меньше самой длинной главы не работает ни при каком k, но жадная проверка этого не заметит: она откроет день с главой, которая в него не помещается, и поиск выдаст предел меньше самой длинной главы.
- «Ровно k дней». Если дней хватает меньше, это тоже подходит: в условии «не больше k».
Алгоритмы задачи
O(log D · стоимость проверки)
2 задачи
PAR
Приём
Жадные алгоритмы
Лучший шаг сейчас без оглядки назад: когда это оптимально, когда почти, и как это доказать.
обычно O(n log n): сортировка или куча
2 задачи