Максимизируйте минимально возможный элемент массива ровно на K декрементов

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

Примеры:

Input: arr[] = {2, 4, 4}, K = 3 
Output: 2
Explanation:
One of the possible way is:

1. Decrement arr[2] by 1. The array modifies to {2, 4, 3}.
2. Decrement arr[1] by 1. The array modifies to {2, 3, 3}.
3. Decrement arr[2] by 1. The array modifies to {2, 3, 2}.

Therefore, the minimum array element that can be obtained is 2, which it is the maximum possible value.

Input: arr[] = {10, 10, 10, 10, 10}, K = 10 
Output: 8

Наивный подход: самый простой подход к решению данной проблемы состоит в том, чтобы перебирать диапазон [1, K] и на каждой итерации находить максимальный элемент массива, а затем уменьшать его на 1 . После вышеуказанных шагов напечатайте минимальный элемент массива.

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

Эффективный подход . Вышеупомянутая проблема также может быть оптимизирована на основе следующих наблюдений:

• Можно заметить, что оптимальный способ — сначала уменьшить все значения массива до минимального элемента массива.
• Общее количество ходов, необходимых для того, чтобы сделать все элементы равными минимальному элементу, представляет собой сумму массива, уменьшенного на K , умноженное на минимальный элемент массива.
• Если общее количество ходов, необходимых для того, чтобы сделать все элементы равными минимальному элементу, меньше K , то ответом будет минимальный элемент.
• В противном случае оптимальным будет уменьшение каждого элемента массива на 1 , пока K не станет равным 0 . Тогда минимальный элемент будет равен .

Следуйте инструкциям, чтобы решить проблему:

• Найдите минимальный элемент массива arr[] и сохраните его в переменной, скажем, minElement .
• Инициализируйте переменную, скажем, reqOperation как 0 , чтобы сохранить общее количество ходов, необходимых для того, чтобы сделать все элементы равными minElement массива.
• Пройдите массив arr[] и на каждой итерации увеличивайте reqOperation на текущий элемент массива, вычитаемый minElement .
• Если reqOperation больше K , выведите minElement . В противном случае выведите значение minElement – (K + N – 1) / N в качестве результирующего минимального элемента.

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

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