Фарбування камінців#250

Фарбування камінців (Розбір)

Зафіксуємо колір $c$ , у який ми хочемо перефарбувати все, і порахуємо, скільки операцій це коштує.

Камінці кольору $c$ ділять ряд на проміжки з камінців інших кольорів. Проміжки обробляються незалежно: операція зачіпає лише дві сусідні позиції, тому «переносити» роботу між проміжками сенсу немає.

Проміжок довжини $L$ вимагає рівно $⌈ L /2 ⌉$ операцій. Справді, кожна операція фарбує щонайбільше дві потрібні позиції, тому менше ніж $⌈ L /2 ⌉$ не буває; і цієї кількості вистачає: беремо позиції парами, а якщо $L$ непарне, останню одиночну позицію фарбуємо разом із сусіднім камінцем кольору $c$ (той свій колір не змінює).

Отже,

cost (c) = проміжки \sum ⌈ \frac{L}{2} ⌉ .

\mathrm{cost}(c) = \sum_{\text{проміжки}} \left\lceil \frac{L}{2} \right\rceil.

Тепер порахуємо це для всіх кольорів швидко. Згрупуємо позиції за кольором. Якщо колір $c$ трапляється на позиціях $q_{1} < q_{2} < \dots < q_{m}$ q_1 < q_2 < \ldots < q_m, то довжини проміжків дорівнюють $q_{1} - 1$ q_1 - 1, потім $q_{s + 1} - q_{s} - 1$ q_{s+1} - q_s - 1, і насамкінець $n - q_{m}$ n - q_m. Для кожного кольору робота пропорційна кількості його входжень, тому сумарно по всіх кольорах виходить $O (n)$ .

Відповідь — мінімум $cost (c)$ по кольорах, наявних у масиві. Перебирати кольори, яких у масиві немає, не потрібно: додаткові входження цільового кольору лише зменшують вартість.

Не забудьте окремий випадок: якщо всі камінці вже однакові, відповідь дорівнює нулю (усі проміжки порожні, і формула дає це автоматично).