В романе N глав. В i-той главе a i страниц. Требуется издать роман в К томах так, чтобы объем самого толстого тома был минимален. Найти объем V самого толстого тома. Делить и переставлять главы нельзя.


ОТВЕТ

Искомая величина — количество страниц V в самом толстом томе. Положим это количество страниц равным какой-то величине L. Попытаемся распределить главы по томам так, чтобы объем каждого тома не превосходил L. Будем заносить в очередной том главы до тех пор, пока добавление следующей главы не приводит к превышению L. После этого перейдем к формированию следующего тома. После того, как все главы будут распределены по томам, мы можем проанализировать то, что у нас получилось.

Если нам удалось распределить все главы по K или менее томам, то L — это оценка для V сверху. 
Если же мы сформировали последний том, и после этого осталась еще хотя бы одна глава, то c максимальным объемом тома не более L страниц главы распределить нельзя. В этом случае L — это оценка для V снизу.

Таким образом, мы можем получить для искомого количества страниц оценки сверху и снизу, а далее действовать методом половинного деления (или, по другому, дихотомии) — мы взяли решение "в вилку", а теперь будем анализировать середину возможного промежутка значений L: если середина дает большее количество томов, чем надо, то она становится новым нижним концом промежутка, иначе — верхним. И в этом случае мы нашли подход к решению задачи, каким-то образом полагая значение искомой величины. Анализ получившегося количества томов показывает, что нужно делать со значением L: уменьшать или увеличивать.