Минимизируйте вычитание элементов массива, чтобы сделать X не более 0
Дано число X и массив arr[] длины N , содержащий N чисел. Задача состоит в том, чтобы найти минимальное количество операций, необходимых для того, чтобы X стало неположительным. За одну операцию:
- Выберите любое число Y из массива и уменьшите X на Y .
- Затем сделайте Y = Y/2 (возьмите минимальное значение, если Y нечетно).
- Если невозможно сделать X неположительным, верните -1 .
Примеры:
Input: N = 3, arr[] = {3, 4, 12}, X = 25
Output: 4
Explanation: Operation 1: Y=12, X reduces to 13, Y becomes 6, arr[]: {3, 4, 6}
Operation 2: Y = 6, X reduces to 7, Y becomes 3, arr[]: {3, 4, 3}
Operation 3: Y = 4, X reduces to 3, Y becomes 2, arr[]: {3, 2, 3}
Operation 4: Y = 3, X reduces to 0, Y becomes 1, arr[]: {1, 2, 3}
Total operations will be 4.Input: N = 3, arr[] = {11, 11, 110}, X = 11011
Output: -1
Explanation: It is impossible to make X non-positive
Подход : Эту проблему можно решить с помощью max-heap (приоритетной очереди) на основе следующей идеи:
To minimize subtraction, it is optimal to subtract the maximum value each time. For this reason use a max-heap so that the maximum value numbers remain on top and perform the operation using the topmost element and keep checking if the number becomes non-positive or not.
Следуйте приведенной ниже иллюстрации для лучшего понимания.
Иллюстрация:
Consider arr[] = {3, 4, 12} and X = 25
So max heap (say P) = [3, 4, 12]
1st step:
=> Maximum element (Y) = 12.
=> Subtract 12 from 25. X = 25 – 12 = 13. Y = 12/2 = 6.
=> P = {3, 4, 6}.2nd step:
=> Maximum element (Y) = 6.
=> Subtract 6 from 13. X = 13 – 6 = 7. Y = 6/2 = 3.
=> P = {3, 3, 4}.3rd step:
=> Maximum element (Y) = 4.
=> Subtract 4 from 7. X = 7 – 4 = 3. Y = 4/2 = 2.
=> P = {2, 3, 3}.4th step:
=> Maximum element (Y) = 3.
=> Subtract 3 from 3. X = 3 – 3 = 0. Y = 3/2 = 1.
=> P = {1, 2, 3}.X is non-positive. So operations required = 4
Следуйте инструкциям, чтобы решить проблему:
- Создайте максимальную кучу (реализованную очередью приоритетов) и сохраните в ней все числа.
- Выполняйте следующие действия до тех пор, пока очередь приоритетов не станет пустой, а X не станет положительным.
- Используйте число, имеющее максимальное значение. Это будет номер в начале приоритетной очереди.
- Удалите верхний номер из очереди приоритетов и выполните операцию, указанную в задаче.
- После выполнения операции, если Y положительный, добавьте ее обратно в очередь приоритетов.
- Каждый раз увеличивайте ответ на 1.
- После завершения вышеуказанного процесса, если X положителен, невозможно сделать его неположительным и, таким образом, вернуть -1.
- В противном случае верните ответ.
Ниже приведена реализация описанного выше подхода.
Временная сложность: O(N * log N)
Вспомогательное пространство: O(N)