Минимальное количество операций, необходимых для того, чтобы сделать массив неубывающим путем добавления 2^i к подмножеству в каждой i-й операции
Дан массив arr[] , состоящий из N целых чисел, задача состоит в том, чтобы найти минимальное количество операций, необходимых для того, чтобы сделать массив неубывающим, выбрав любое подмножество массива arr[] и добавив 2 i всем элементам подмножества на i -м шаге.
Примеры:
Input: arr[ ] = {1, 7, 6, 5}
Output: 2
Explanation:
One way to make the array non-decreasing is:
- Increment arr[1] and arr[3] by 20. Thereafter, the array modifies to {2, 7, 6, 6}.
- 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:
- 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.
- 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].
- 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)