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

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

Дано число 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)

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