Люблять, не люблять (Editorial)

Автор: Андрій Холод

Роздробник: Андрій Холод

Розбір підготовано: Костянтин Денисов

Нехай M=\max(a_1,\dots,a_n).

За одну операцію будь-який елемент зменшується не більше ніж на $1$, тому елемент зі значенням $M$ потребує щонайменше $M$ операцій. З іншого боку, рівно за $M$ операцій занулити масив завжди можна: кожного разу беремо другу операцію з найлівішого індексу, де a_i>0. Тоді поточний максимум зменшується на $1$ на кожному кроці, отже через $M$ кроків стане $0$, а раз максимум $0$, то всі елементи теж $0$. Тому мінімальна кількість операцій (без вимоги про непарність) дорівнює $M$.

Тепер потрібна непарна кількість операцій.

• Якщо n=1, то кількість операцій завжди рівно $M$ (бо зменшувати можна тільки цей єдиний елемент). Тому відповідь існує тоді і тільки тоді, коли $M$ непарне; у цьому випадку мінімум $M$.

• Якщо n>1:

  • якщо $M$ непарне, то вже підходить відповідь $M$;

  • якщо $M$ парне, то робимо одну зайву першу операцію на будь-якому елементі, який не є тим єдиним елементом з максимумом (тобто зменшуємо не «вирішальний» максимум), після чого все одно можна занулити масив за $M$ операцій. Отже мінімальна непарна відповідь дорівнює M+1.

Отже алгоритм простий: знайти $M$. Якщо n=1, відповідаємо YES і $M$ лише коли $M$ непарне, інакше NO. Якщо n>1, завжди YES, а відповідь дорівнює $M$, якщо $M$ непарне, і M+1, якщо $M$ парне.

Складність. Один прохід по масиву, $O(n)$ часу та $O(1)$ пам'яті.