Коригування масивів#23

Коригування масивів (Editorial)

Кожен елемент можна залишити як є або змінити йому знак, тобто для позиції доступні рівно два значення: |a_i| та -|a_i|. Замінимо одразу всі числа на модулі — це нічого не змінює, зате спрощує міркування.

Тепер працює жадібний підхід: ідемо зліва направо і на кожній позиції беремо найменше допустиме значення, яке не менше за попереднє. Чим менше поточне число, тим більше свободи залишиться далі, тому такий вибір ніколи не шкодить.

Конкретно, нехай — значення, обране на попередній позиції. Для поточної позиції:

  • якщо -|a_i| \ge p, беремо -|a_i| — це менший із двох варіантів;

  • інакше, якщо |a_i| \ge p, беремо |a_i|;

  • інакше обидва варіанти менші за , послідовність побудувати неможливо — виводимо NO.

Для першого елемента попереднього значення немає, тому одразу беремо -|a_1| як найменше можливе.

Якщо дійшли до кінця, виводимо YES і сам масив. Складність — , чого достатньо при N \le 100\,000.

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