Подсчитайте минимальный префикс или суффикс уменьшения или увеличьте все операции, чтобы сделать массив равным 0
Дан массив arr[] размера N . Задача состоит в том, чтобы сделать все элементы массива равными нулю, применяя минимальное количество операций.
Допускаются следующие операции:
- Выберите индекс i и уменьшите каждый элемент на 1 для префикса до этого индекса.
- Выберите индекс i и уменьшите каждый элемент на 1 для суффикса, начинающегося с этого индекса.
- Увеличьте все элементы массива на 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 = 12Input: 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)