Минимизируйте операции, чтобы уменьшить сумму массива наполовину, уменьшив любые элементы наполовину

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

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

Примеры:

Input: Arr[] = [4, 6, 3, 9, 10, 2]
Output: 5
Explanation: The initial sum = (4+6+3+9+10+2) = 34
1st step: choose 10 and make it 5, sum = 29
2nd step: choose 9 and make it 4, sum = 24
3rd step: choose 6 and make it 3, sum = 21
4th step: choose 5 and make it 2, sum =18
5th step: choose 4 and make it 2, sum =16

Input: Arr[] = [1, 5, 8, 19]
Output: 3

Подход: идея решить проблему заключается в использовании структуры данных кучи.

The target is to reduce the number of operations to make the sum of the array half, thus,  

  • At every operation the amount of reduction of the sum value should be as high as possible. 
  • To achieve that, try to choose the maximum value available on the array and reducing it to its half value. 
  • The best way to find the maximum value at every iteration is to use apriority_queueas a max-heap as max-heap will store the maximum value of the array at the top of the max-heap.

Чтобы реализовать этот подход, выполните следующие шаги, показанные ниже:

  • Вычислите сумму элементов массива, перебирая массив.
  • Инициализируйте max-heap с помощью priority_queue для хранения всех элементов массива.
  • Инициализируйте переменную счетчика в 0, эта переменная будет хранить минимальное количество операций.
  • Поскольку вершина максимальной кучи всегда будет содержать максимальный элемент, присутствующий в массиве, удалите верхний элемент, сделайте его половинным (целочисленное деление) и введите новое значение в максимальную кучу.
  • Продолжайте этот предыдущий шаг, пока сумма элементов не станет меньше или равна ее начальному значению.

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

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

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