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

Учитывая циклический массив arr[] из N целых чисел и массив cost[] , задача состоит в том, чтобы вычислить минимальное количество операций, необходимых для того, чтобы все элементы массива были равны 0 , где при каждой операции уменьшается значение индекса i на 1 . Если значение индекса становится равным 0, уменьшите значение arr[i+1] на cost[i] , уменьшите значение arr[i + 2] на cost[i + 1] и так далее.

Примечание. Если элемент становится меньше 0, он считается равным 0.

Пример:

Input: arr[] = {7, 2, 5}, cost[] = {8, 9, 3}
Output: 6
Explanation: Decrements can be made in the following way:

• Decrement the value of arr[1] twice. Hence, the value of arr[2] will be decremented by cost[1] and the value of arr[0] will be decremented by cost[2]. Therefore, the final array will be arr[] = {4, 0, 0}.
• Now, decrement the value of arr[0], 4 times to make it 0. Therefore, the array becomes arr[] = {0, 0, 0}.

Hence, the number of required operations to make all the elements of the array equal to zero is 6 which is the minimum possible.

Input: arr[] = {6, 7, 7, 10, 8, 2}, cost[] = {5, 10, 1, 4, 7, 7}
Output: 16

Подход: данная проблема может быть решена с использованием жадного подхода с помощью следующих наблюдений:

• Последний оставшийся ненулевой элемент массива arr[] , предположим, x потребует x операций уменьшения.
• Предположим, что после операций декремента значение arr[i] становится равным 0 , тогда для arr[i] требуемое количество декрементов равно arr[i] , для arr[i+1] необходимое количество декрементов будет arr [i+1] – max(0, arr[i+1] – cost[i]) и так далее.

Ниже приведены шаги, которые необходимо выполнить:

• Пройдите по заданному массиву arr[] в диапазоне [0, N), используя переменную i .
• Количество операций, необходимых для того, чтобы сделать i ^-й индекс массива равным нулю, равно arr[i] – min(arr[i], cost[i-1]) . Поэтому сохраните сумму этого значения по всем индексам в переменной ans .
• Увеличьте значение ans на минимальное значение arr[i] или cost[i] по всем индексам в диапазоне [0, N) .

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

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