CS
Задачник Базовый курс EN

Задача

Ровный заголовок

двоичный поиск жадность редакторы текста в проде

Браузер с text-wrap: balance выравнивает заголовок так. Сначала он переносит текст жадно в колонке шириной W: в строку кладётся столько слов, сколько помещается. Пусть вышло k строк. Затем он ищет самую узкую колонку, в которой тот же жадный перенос даёт не больше k строк, и набирает текст в ней: строк столько же, а их длины ближе друг к другу.

Найдите ширину этой самой узкой колонки. Слово i занимает ai знаков, между словами в строке — один пробел, строка не может быть длиннее колонки.

Вход

В первой строке — n и W (1 ≤ n ≤ 5·104, 1 ≤ W ≤ 109). Во второй — n длин слов (1 ≤ ai ≤ min(W, 104)).

Выход

Одно число — наименьшая ширина колонки, в которой жадный перенос даёт не больше k строк.

В первом примере — заголовок «Как разбить абзац на строки так, чтобы правый край был ровным» в колонке из 30 знаков. Жадно выходит три строки, последняя — одно слово «ровным». В колонке из 22 знаков строк тоже три: «Как разбить абзац на / строки так, чтобы / правый край был ровным», а в колонке из 21 — уже четыре.

Примеры

Пример 1

Вход
11 30
3 7 5 2 6 4 5 6 4 3 6
Выход
22

Пример 2

Вход
3 20
10 15 5
Выход
15

Ограничения

Время · Python
6000 мс
Время · Go
1000 мс
Память
256 МБ
Проверка
10 тестов

Разбор

Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.

1Подсказка 1

Может ли в более широкой колонке жадный перенос дать больше строк, чем в узкой?

2Идея

Не может. Жадный перенос даёт наименьшее возможное число строк при данной ширине — это доказано в статье. А любое разбиение, которое помещается в узкую колонку, помещается и в широкую, поэтому наименьшее число строк с ростом ширины не растёт. Значит, условие «жадно не больше k строк» монотонно по ширине: если оно выполнено при w, то и при любой большей. Самую узкую такую ширину находит двоичный поиск по ответу.

3Разбор

Считаем k — число строк жадного переноса при ширине W. Ищем ответ на отрезке от самого длинного слова (в более узкой колонке оно не поместится) до W (там условие выполнено). На каждом шаге проверяем середину одним жадным проходом. Так и делает Chromium: по описанию в блоге разработчиков Chrome, он двоичным поиском ищет самую узкую ширину, которая не добавляет строк.

3+Решение
4Сложность

Один жадный проход — O(n), проходов — O(log W), около 30: всего O(n log W).

5Типичные ошибки
  • Поделить поровну. Длина текста, делённая на k, — нижняя граница, но слова не режутся, и при такой ширине жадный перенос часто даёт лишнюю строку. Первый пример: поровну выходит 21, а нужно 22.
  • Искать ниже самого длинного слова. Там строка с этим словом не помещается ни в какой колонке; при правильной нижней границе такой случай не возникает.
  • Подбирать ширину шагами по одному знаку. Ответ тот же, но при W до 109 это миллиард жадных проходов.

Алгоритмы задачи

DP Алгоритм Красивый перенос строк Жадный перенос против всего абзаца сразу: кратчайший путь по местам разрыва, как в TeX. O(n·L) 2 задачи SRT Приём Двоичный поиск по ответу Если проверить ответ легче, чем найти, и проверка монотонна, — ищем ответ делением пополам. O(log D · стоимость проверки) 2 задачи PAR Приём Жадные алгоритмы Лучший шаг сейчас без оглядки назад: когда это оптимально, когда почти, и как это доказать. обычно O(n log n): сортировка или куча 2 задачи
Каталог алгоритмов