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

По трем числам N , K и M задача состоит в том, чтобы найти максимальное значение, которое можно присвоить K- му индексу, если всем N индексам присваиваются положительные значения так, что общая сумма значений меньше M , а разность между значениями в соседних позициях не больше 1.

Примеры:

Input : N=3, M=10, K=2
Output: 4
Explanation: The optimal way to assign values is {3, 4, 3}. Total sum=3+4+3=10≤M. 
Note: {3, 4, 2} is not a valid distribution as 4-2=2>1

Input: N=7, M=100, K=6 
Output: 16

Подход : В решении проблемы помогают следующие наблюдения:

1. Если X присваивается K- му индексу, то оптимальное распределение выглядит следующим образом:
   1. Если X меньше K-1 , оптимальное распределение слева будет (X-1), (X-2), …(X-K+1), (1), (1)…
   2. В противном случае это было бы (X-1), (X-2), …(X-K+1) .
   3. Если X меньше NK , оптимальное распределение слева будет (X-1), (X-2), …(X-N+K), 1, 1…
   4. В противном случае это было бы (X-1), (X-2), …(X-N+K) .
2. Используя ряд AP, сумма (X-1)+(X-2)+(X-3)+…+(XY) равна Y*(X-1+XY)/2 = Y*(2X-Y -1)/2

Максимальное значение X можно рассчитать с помощью концепции бинарного поиска. Выполните следующие шаги, чтобы решить проблему:

1. Инициализируйте переменную как -1 , чтобы сохранить ответ.
2. Инициализируйте две переменные низким значением 0 и высоким значением M для целей двоичного поиска.
3. Цикл while low не больше high и делаем следующее:
   1. Вычислите mid как среднее значение high и low .
   2. Инициализируйте переменную val значением 0 , чтобы сохранить текущую сумму распределения.
   3. Инициализируйте L (количество индексов слева от K ) как K-1 и R (количество индексов справа от K ) как NK .
   4. Добавьте значение mid к val .
   5. Распределите числа слева и справа от K , как обсуждалось выше, и добавьте их значения к val .
   6. Если val меньше, чем M , обновить ans как максимальное из ans и mid . Обновите низкий уровень как mid+1 .
   7. В противном случае обновите high до mid-1 .
4. Возврат ответ .

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

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