Подсчитайте минимальный префикс или суффикс уменьшения или увеличьте все операции, чтобы сделать массив равным 0

Опубликовано: 26 Февраля, 2023

Дан массив arr[] размера N . Задача состоит в том, чтобы сделать все элементы массива равными нулю, применяя минимальное количество операций.
Допускаются следующие операции:

  1. Выберите индекс i и уменьшите каждый элемент на 1 для префикса до этого индекса.
  2. Выберите индекс i и уменьшите каждый элемент на 1 для суффикса, начинающегося с этого индекса.
  3. Увеличьте все элементы массива на 1.

Примеры:

Input: arr[] = {2, 4, 6, 3, 7}
Output: Minimum operations: 12
Explanation: Select Index 0, and decrease all the elements from 
index 1 to 4 by 2 in 2 operations, new arr[] would be {2, 2, 4, 1, 5}.
Select Index 1, and decrease all the elements from index 2 to 4 
by 2 in 2 operations, new arr[] would be {2, 2, 2, -1, 3}
Select Index 3, and decrease all the elements from index 0 to 2
by 3 in 3 operations, new arr[] would be {-1, -1, -1, -1, 3}
Select Index 3, and decrease element of index 4 by 4 in 4 operations,  
New arr[] would be {-1, -1, -1, -1, -1}
Increase all the elements by 1 in 1 operation,  
Final arr[] would be {0, 0, 0, 0, 0}
Total, operations would be 2 + 2 + 3 + 4 + 1 = 12

Input: arr[] = {1, 3, 5, 7, 5, 2, 8} 
Output: Minimum operations:  21 

Подход:

Следующая задача может быть решена с помощью жадного подхода.

Initially make all elements equal to the first element and then decrement them to have value as 0.

Для этого можно предпринять следующие шаги:

  • Чтобы сделать все элементы равными первому элементу, мы будем использовать разницу между последовательными элементами. ( обр[i+1] – обр[i] ).
  • Если разница (diff = arr[i+1] – arr[i]) положительна, уменьшаем элементы суффикса, начиная с индекса (i+1) .
    • Требуемое количество операций = абс (разн.)
  • Если разность (diff = arr[i+1] – arr[i]) отрицательна, уменьшаем элементы префикса до индекса i .
    • Требуемое количество операций = abs( diff ) . Уменьшение префикса также уменьшит первый элемент массива на abs( diff) .
  • Наконец, общее количество требуемых операций будет вычисляться как абсолютная разница между последовательными элементами массива плюс абсолютное значение первого элемента массива.

Ниже приведена реализация вышеуказанного подхода:

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

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