Минимальные операции для получения суммы массива не более S из заданного массива

Учитывая массив arr[], размера N и целое число S , задача состоит в том, чтобы найти минимальные операции, чтобы сделать сумму массива меньше или равной S. В каждой операции:

• Можно выбрать любой элемент и уменьшить его на 1 или
• Может быть заменен любым другим элементом массива.

Примеры:

Input: arr[]= {1, 2, 1 ,3, 1 ,2, 1}, S= 8
Output: 2
Explanation: Initially sum of the array is 11.
Now decrease 1 at index 0 to 0 and Replace 3 by 0. 
The sum becomes  7 < 8. So 2 operations.

Input: arr[] = {1,2,3,4}, S= 11
Output: 0
Explanation: Sum is already < =11 so 0 operations.

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

First sort the array. Consider performing x operations of 1st type on the arr[0] and then performing the 2nd operation on the suffix of the array of length i. Also consider the sum for this suffix of length i is sufSum.

Sum of the modified array must be <=S
So, the difference to be  subtracted from the sum must be (diff)>= sum – S.

If x operations of type 1 is done on minimum element and type 2 operations are done the suffix of the array from [i,n) the sum of the decreased array is 

cost = x + s – (n-i) * (a[0] – x)
cost = (n-i+1)* x-(n-i)* a[0]  +s
cost >= sum – S = diff
s – (n-i) * a[0] + (n-i+1) *x >= diff 
so x >= (diff – s+(n-i)* a[0]) / (n-i+1)

The minimum value of x is x = ceil((diff -s+ (n-i)* a[0]) / (n-i+1))

So the total operations are x (type-1) + (n-i) type-2 

Выполните следующие действия, чтобы решить вышеуказанные проблемы:

• Инициализируйте переменную sum = 0 и размер массива до N .
• Перебрать вектор и найти сумму массива.
• Если сумма < = S , выведите 0 и вернитесь.
• Отсортируйте вектор и назначьте diff = sum-S .
• Инициализируйте ops = sum-S , что является максимально возможным количеством операций.
• Инициализируйте s =0 , в котором хранится сумма суффиксов вектора.
• Теперь перейдите от конца вектора, используя цикл for.
• Следите за суммой суффиксов в переменной s .
• Инициализировать переменную dec , которая представляет собой значение, которое будет уменьшено с суффикса массива.
  • Если s-dec больше или равно diff , нет необходимости уменьшать значение arr[0] , поэтому присвойте x =0 .
  • В противном случае найдите значение x , которое является значением, подлежащим уменьшению в arr[0] , и найдите минимальные операции.
• Распечатать минимальные операции

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

Временная сложность: O(N*logN)
Космическая сложность: O(1)