Минимум операций, чтобы сделать произведение пары соседних элементов суммы префикса отрицательной

Опубликовано: 22 Сентября, 2022

Дан массив arr[ ] размера N , рассмотрим массив prefix[ ], где prefix[i] представляет собой сумму первых i элементов массива arr . Задача состоит в том, чтобы найти минимальное количество операций, необходимых для модификации заданного массива так, чтобы произведение любых двух соседних элементов в массиве префиксов было отрицательным. За одну операцию вы можете увеличить или уменьшить значение любого элемента на 1.

Input: arr[] = {1, -3, 1, 0}
Output: 4
Explanation: The sequence can be transformed into 1, -2, 2, -2 by 4 operations, the sum of the prefixes are 1, -1, 1, -1 which satisfy all the conditions.

Input: arr[] = {-1 4 3 2 -5 4}
Output: 8

Подход: Идея состоит в том, чтобы опробовать две независимые возможности: суммы префиксов четной длины положительны, а суммы префиксов нечетной длины отрицательны, или наоборот. Выполните следующие шаги, чтобы решить проблему:

  • Инициализируйте переменную res = INT_MAX для хранения минимального количества операций.
  • Пройдите через диапазон [0, 1], используя переменную r.
    • Инициализируйте переменные ans = 0 и sum = 0 , чтобы сохранить общее количество операций и текущую сумму префикса соответственно.
    • Пройдите через диапазон [0, N-1], используя переменную i,
      • Добавьте arr[i] к значению sum .
      • Если значение (i+r) нечетное и если сумма не положительна, добавьте сумму +1 к ответу и обновите значение суммы до 1.
      • В противном случае, если (i+r) четно и сумма неотрицательна, добавьте сумму+1 и обновите значение суммы до -1.
    • Обновите значение res как min(res, ans).
  • После выполнения вышеуказанных шагов выведите значение res .

Временная сложность: O(N)
Вспомогательное пространство: O(1)

РЕКОМЕНДУЕМЫЕ СТАТЬИ