Адміністративна реформа#151

Адміністративна реформа (Editorial)

Міста стоять на прямій у порядку зростання координат, а регіон — це відрізок послідовних міст. Тому «максимальна відстань між містами регіону» — це просто різниця координат крайніх міст цього регіону.

Задача — розбити послідовність на послідовних блоків завдовжки від до міст так, щоб найбільша з таких різниць була мінімальною. Це природно розв'язується динамічним програмуванням.

Нехай \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}[i][j] = \min_{A \le l \le B} \max\bigl(\mathrm{dp}[i-l][j-1],\; x_i - x_{i-l+1}\bigr).

Відповідь — \mathrm{dp}[N][K]; якщо вона залишилась нескінченністю, розбиття не існує.

Складність — \mathcal{O}(N \cdot K \cdot B) станів і переходів.

Альтернативний підхід — двійковий пошук за відповіддю: зафіксуємо межу і перевіримо жадібно чи динамікою, чи можна розбити міста на рівно регіонів так, щоб кожен мав розкид не більший за . Функція монотонна, тому двійковий пошук коректний; він корисний, якщо добуток N \cdot K \cdot B завеликий.

Координати сягають 10^9, тому різниці вміщуються у 32-бітний тип, але «нескінченність» краще брати з запасом у 64-бітному.