Минимальное количество операций, необходимых для того, чтобы сделать массив неубывающим путем добавления 2^i к подмножеству в каждой i-й операции

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

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

Примеры:

Input: arr[ ] = {1, 7, 6, 5}
Output: 2
Explanation:
One way to make the array non-decreasing is:

  1. Increment arr[1] and arr[3] by 20. Thereafter, the array modifies to {2, 7, 6, 6}.
  2. Increment arr[2] and arr[3] by 21. Thereafter, the array modifies to {2, 7, 8, 8}.

Therefore, two operations are needed to make the array non-decreasing. Also, it is the minimum count of operations.

Input: arr[ ] = {1, 2, 3, 4, 5}
Output: 0

Подход: Данная проблема может быть решена на основе следующих наблюдений:

Supposing A[] as the original array and B[] as the final, then:

  1. There will be only one way to make the final non-decreasing array, because there is no more than a single way to make a specific amount of addition to a number. Therefore, the task will be to minimize the max(B1−A1, B2−A2, …, Bn−An), as smaller differences lead to the use of shorter time to make the array non-decreasing.
  2.  B[] is optimal when B[i] is the maximum value between B1, B2, …, B[i]−1 and A[i] because for each position i,  B[i]−A[i] should be as small as possible and B[i-1] ≤ B[i] and A[i] ≤ B[i].
  3. If X operations are performed, then any array element can be increased by any integer in the range [0, 2X-1].

Выполните следующие шаги, чтобы решить проблему:

  • Инициализируйте переменную, скажем, val как 0 , чтобы сохранить максимальную разницу между конечными элементами массива и исходными элементами массива с теми же индексами.
  • Инициализируйте другую переменную, скажем, mx как INT_MIN, чтобы сохранить максимум префикса массива.
  • Обходим массив arr[] с помощью переменной i и на каждой итерации обновляем mx до max(mx, arr[i]) и val до max(val, mx – arr[i]) .
  • Наивысшая степень числа 2, меньшая, чем целое число, val, а затем сохраните ее в переменной, скажем, res .
  • Наконец, после выполнения вышеуказанных шагов выведите значение res в качестве ответа.

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

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

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