Міста стоять на прямій у порядку зростання координат, а регіон — це відрізок послідовних міст. Тому «максимальна відстань між містами регіону» — це просто різниця координат крайніх міст цього регіону.
Задача — розбити послідовність на послідовних блоків завдовжки від до міст так, щоб найбільша з таких різниць була мінімальною. Це природно розв'язується динамічним програмуванням.
Нехай \mathrm{dp}[i][j] — мінімально можлива максимальна відстань, якщо перші міст уже розбито на регіонів. База: \mathrm{dp}[0][0] = 0, решта — «нескінченність».
Перехід: останній регіон складається з міст, де A \le l \le B. Він охоплює міста від i - l + 1 до , а його «ціна» — це x_i - x_{i-l+1}. Оскільки нас цікавить максимум по регіонах, беремо
Відповідь — \mathrm{dp}[N][K]; якщо вона залишилась нескінченністю, розбиття не існує.
Складність — \mathcal{O}(N \cdot K \cdot B) станів і переходів.
Альтернативний підхід — двійковий пошук за відповіддю: зафіксуємо межу і перевіримо жадібно чи динамікою, чи можна розбити міста на рівно регіонів так, щоб кожен мав розкид не більший за . Функція монотонна, тому двійковий пошук коректний; він корисний, якщо добуток N \cdot K \cdot B завеликий.
Координати сягають 10^9, тому різниці вміщуються у 32-бітний тип, але «нескінченність» краще брати з запасом у 64-бітному.