Додавання#75

Додавання (Editorial)

Мінімізувати кількість операцій не потрібно — вистачає вкластися у . Це підказує розв'язок у два етапи по операцій.

Головна перешкода — від'ємні числа: якби всі елементи були невід'ємними, масив легко зробити неспадним префіксними сумами. Тому спершу позбудемось різнознакових елементів.

Випадок 1: |\max| \ge |\min|. Візьмемо індекс з найбільшим значенням a_t = \max. Для кожного від'ємного елемента виконаємо a_i \mathrel{+}= a_t. Оскільки a_t \ge |a_i|, після цього a_i \ge 0. Витрачено щонайбільше операцій, і тепер увесь масив невід'ємний.

Далі йдемо зліва направо і для від до n-1 виконуємо a_{i+1} \mathrel{+}= a_i. Оскільки a_i \ge 0, маємо a_{i+1} \ge a_i — масив стає неспадним. Це ще n - 1 операція, разом менше ніж .

Випадок 2: |\max| < |\min|. Симетрично. Візьмемо індекс з найменшим значенням і додамо a_t до всіх додатних елементів — масив стане цілком недодатним. Тепер ідемо справа наліво: для від n-1 до виконуємо a_i \mathrel{+}= a_{i+1}. Оскільки a_{i+1} \le 0, отримуємо a_i \le a_{i+1}, тобто знову неспадання.

Виводимо кількість операцій і сам їх список. Зверніть увагу, що умова дозволяє k = 0, якщо масив уже впорядкований, але й «зайві» коректні операції теж приймаються — головне не перевищити .