Минимум операций для преобразования элементов массива в 0 путем уменьшения пары или одного элемента
Учитывая массив 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)