Пояснения.
Все алгоритмы лежат в файле solve.js
- Получаем массив длин слов (функция getWordLengths, строка 45). К каждому слову справа добавляется пробел, потому в массиве каждое число на 1 больше. Если слово длиннее constraint, то при выставленной галке "переноса слов" разбиваем его на куски. Т.к. в конце абзаца нет пробела, то для решения задачи далее будем использовать constraint+1. Теперь у нас есть массив натуральных чисел, и надо разбить его на отрезки, суммы которых не превышают constraint+1.
С этим массивом работает функция balancedSplitArray, строка 79.
-
Вычисляем суммы элементов массива (строка 85), сохраняем в массив sums.
-
Делаем "жадное" разбиение (строка 96). Просто идем от начала, набираем элементы, пока помещаются в constraint+1, их группируем в абзац. Получили, во первых, то самое, минимальное количество абзацев, во вторых, массив splittersMax - самые крайние справа возможные значения разделителей. Аналогичное делаем с конца массива, получаем splittersMin. Если в этих двух массивах все значения совпадают, то больше искать нечего, выходим.
-
Теперь имеем стандартную проблему "линейного разбиения" - разбить массив на столько-то частей по возможности равномерно. Берем среднюю длину абзаца (avg), и будем минимизировать сумму квадратов отклонений длин абзацев от этой средней (обозначим это M). Используем подходы динамического программирования и рекуррентное сотношение. Если в массиве n элементов и надо разбить на k кусков, то M(n, k) = M(n-m, k-1) + (Sum(n-m+1 ... n) - avg) ^ 2
где Sum(a ... b) легко вычисляется как sums[b] - sums[a]
Для этой формулы остается подобрать такое m (значение последнего разделителя), при котором значение M(n, k) будет минимально. M(n-m, k-1) вычисляется аналогично, как оптимальная разбивка массива из n-m элементов на k-1 кусков.
Это находится перебором (строка 152). Вычисленные значения сохраняем в таблицу weights, для последующего использования. В таблице splitters будут те значения разделителей, которые соответствуют минимумам в weights.
В классическом варианте задачи перебор для каждого разделителяведется по всей длине массива, но у нас есть splittersMin и splittersMax, которые сильно сужают облать поиска.
В после перебора из таблицы splitters получаем значения разделителей (строка 183), а по этим разделителям функция applySplitters разрезает исходную строку.