Минимизируйте максимум массива, выполнив не более K увеличения и уменьшения

Дан положительный массив arr[] размера N (2 ≤ N ≤ 10 ⁵ ) и натуральное число K , задача состоит в том, чтобы минимизировать максимальное значение arr[] , выполнив не более K операций, где в каждой операции можно выбрать любые два различных целых числа i и j (0 ≤ i, j < N) , затем увеличьте значение arr[i] на 1 и уменьшите значение arr[j] на 1 .

Пример:

Input: arr = {3, 3, 7, 1, 6}, k = 2
Output: 6
Explanation:
One set of optimal operations is as follows:
For K = 1 => Select i = 2 and j = 0  and arr becomes {4, 3, 6, 1, 6}.
For K = 2 => Select i = 4 and j = 3, and arr becomes {4, 3, 6, 2, 5}.
The maximum integer of nums is . It can be shown that the maximum number cannot be less than 6.
Therefore, we return 6.

Input: nums = {10, 1, 1}, k = 3
Output: 7

Подход: Задача может быть решена с помощью бинарного поиска, основанного на следующей идее.

Choose the minimum and maximum possible value in start and end variable respectively. Find the mid value of start and end. Check if we can choose mid as the maximum possible value in array. If its true then this is one of our valid answer. So update our answer in result and shift the start to mid – 1 to minimise the maximum possible value. Otherwise shift the end to mid + 1. Finally return the result.

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

• Инициализировать переменную start = 0, end = максимальное значение в arr[] и результат
• Пока start меньше, чем end , сделайте следующее
  • Вычислить середину по (начало + конец) / 2
  • Проверьте, может ли mid быть допустимым максимальным значением, следующим образом:
    • Инициализировать переменную operationCount = 0
    • Перебрать массив arr[]
      • Проверьте, превышает ли arr[i] ожидаемый максимум середина
        • OperationCount += mid – обр[i]
      • Проверьте, больше ли OperationCount , чем K .
        • Если правда, вернуть ложь
    • Вернуть истину
  • Если mid является допустимым максимально возможным значением, то
    • Сдвиг конца в середину – 1
    • сохранить середину в результате
  • В противном случае сдвиньте начало на середину + 1
• Вернуть результат

Ниже приведена реализация описанного выше подхода.

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

Статьи по Теме:

• Введение в массивы - учебные пособия по структурам данных и алгоритмам
• Бинарный поиск