Минимум операций для преобразования элементов массива в 0 путем уменьшения пары или одного элемента

Опубликовано: 26 Февраля, 2023

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

  • Уменьшите 2 разных элемента массива на один.
  • Уменьшить один элемент массива на один.

Пример:

Input: arr[] = {1, 2, 3}, N = 3
Output: 3
Explanation : Operation 1: reduce 3 and 2 to get {1, 1, 2}
Operation 2: reduce 1 and 2 to get {1, 0, 1}
Operation 3: reduce both 1s to get {0, 0, 0}

Input: arr[] = {5, 1, 2, 9, 8}, N = 5
Output: 13

Подход:

This problem can be solved using greedy approach. The idea is to reduce the 2 largest elements at a time or (if not possible) 1 at a time.  As we need the largest elements in each step, we can use a max heap.

Для решения этого подхода можно предпринять следующие шаги:

  • Инициируйте переменную count как 0 .
  • Вставьте все элементы в максимальную кучу.
    • Уменьшите два самых больших элемента.
    • Вставьте уменьшенные значения снова в кучу.
  • Повторяйте вышеупомянутые шаги, пока все элементы массива не станут равны нулю, и увеличивайте количество на каждой итерации.
  • Остановиться, когда все элементы массива равны нулю.

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

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

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