Пограбування масиву#177

Пограбування масиву (Розбір)

Масив складається лише з нулів та одиниць і впорядкований за неспаданням, тому він має вигляд \underbrace{0 \ldots 0}_{z} \underbrace{1 \ldots 1}_{o}. Сума дорівнює кількості одиниць, тож умова «сума парна» означає просто, що одиниць парна кількість.

Спочатку перевіримо сам масив : якщо він не є неспадним, то жодним додаванням це не виправити — відповідь .

Далі нехай у рівно нулів та одиниць. Розглянемо два випадки.

Якщо парне, то вже задовольняє всі умови — це один спосіб (нічого не додавати). Додавання одиниці зробило б суму непарною, а от нуль суму не змінює. Вставляти нуль треба серед нулів, щоб масив залишився неспадним, а проміжків між (і навколо) нулів рівно z + 1. Разом

1 + (z + 1) = z + 2.

Якщо непарне, то ні залишити масив як є, ні додати нуль не можна — сума лишиться непарною. Треба додати одиницю, і вставити її можна лише серед одиниць, тобто в один із o + 1 проміжків. Разом

o + 1.

Складність — : досить одного проходу, щоб перевірити впорядкованість і порахувати нулі та одиниці.