Минимизируйте декременты, чтобы все элементы массива были одинаковыми или равными 0

Опубликовано: 19 Сентября, 2022

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

Примеры :

Input: arr[] = {4, 1, 6, 6}
Output: 5
Explanation: Remove 1 from arr{1}, array becomes, {4, 0, 6, 6}, makes 1 operation. 
Remove 2 from arr[2], arr[] = {4, 0, 4, 6}, in 2 operations. 
Remove 2 from arr[3], arr[] = {4, 0, 4, 4} in 2 operations.
So, Total operations = 1 + 2 + 2 = 5.

Input: arr = {1, 1, 2, 10}
Output: 4
Explanation: Remove 1 from arr[0], 1 from arr[1] and 2 from arr[2]. Total operations = 1 + 1 + 2 = 4

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

  • If each element of the array is taken as the value that must be equal to the rest of the array elements,
  • Then total removal for any index i would be the (sum_array – (N – i)*arr[i])
  • So the approach would be just to find the above value for each index and return the minimum among them.

Выполните шаги, указанные ниже, чтобы решить проблему:

  • Отсортируйте заданный массив.
  • Вычислите сумму всех элементов массива и сохраните ее в переменной, скажем, total_sum .
  • Создайте переменную Minimum_operation = INT_MAX , запустите цикл и обновите Minimum_operation = min(minimum_operation, total_sum – (N – i)*arr[i])
  • В качестве ответа верните Minimum_operation .

Ниже приведена реализация описанного выше подхода.


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

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