Максимизируйте наименьший элемент массива, увеличив все элементы в подмассиве длины K на 1 ровно M раз

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

Примеры:

Input: arr[ ] = {2, 2, 2, 2, 1, 1}, M = 1, K = 3
Output: 2
Explanation: Update the last 3 elements on the first move then updated array is [2, 2, 2, 3, 2, 2]. The smallest element has a value of 2.

Input: arr[ ] = {5, 8}, M = 5, K = 1
Output: 9

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

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

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