Найти сумму массива после увеличения на K соседних элементов каждого положительного элемента M раз

Дан круговой массив arr[] из N целых чисел и два целых числа M и K , задача состоит в том, чтобы найти сумму элементов массива arr[] после выполнения M операций так, чтобы в каждой операции увеличивать соседние элементы массива всех положительных элементов массива на K , т. е. если arr[i ] > 0 , затем увеличьте значение arr[i – 1] и arr[i + 1] на K .

Примеры:

Input: arr[] = {0, 1, 0, 1, 0, 0}, M = 2, K = 1
Output: 16
Explanation: 
In the 1st operation after incrementing the adjacent array elements of arr[] > 0, the given array modifies to arr[] = {1, 1, 2, 1, 1, 0}. 
In the 2nd operation after incrementing the adjacent array elements of arr[] > 0, the given array modifies to arr[] = {2, 3, 4, 3, 2, 2}. So the sum of all elements of arr[] is 16.

Input: arr[] = {1, 2, 3}, M = 10, K = 2
Output: 126

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

• Любой ненулевой элемент всегда будет увеличивать сумму массива на 2 * K за один ход.
• Количество ходов, необходимых для увеличения целого числа от 0 до ненулевого значения, всегда равно расстоянию до ближайшего ненулевого элемента.

Выполните следующие шаги, чтобы решить проблему:

• Создайте массив steps[] , в котором хранится расстояние текущего элемента от ближайшего ненулевого элемента.
• Создайте функцию NearestLeft() для поиска индекса ближайшего ненулевого элемента при обходе массива влево, используя подход, обсуждаемый в этой статье.
• Аналогичным образом создайте функцию NearestRight() для поиска индекса ближайшего ненулевого элемента при обходе массива в правильном направлении.
• Количество операций, необходимых для увеличения значения i ^-го элемента от 0 , задается steps[i] , и после этого оно будет вносить 2 * K в окончательную сумму после каждой операции. Таким образом, общий вклад i ^-го числа в итоговую сумму после M операций равен 2 * K * (M – steps[i]) .
• Пройдите массив arr[] в диапазоне [1, N] и отследите сумму, вносимую каждым индексом в переменную, скажем, sum .
• После выполнения вышеуказанных шагов выведите в качестве результата значение sum .

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

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