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

Опубликовано: 21 Сентября, 2022

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

Примечание. Обязательно выполнять операцию разделения до тех пор, пока размер массива arr[] не станет ≥ K .

Примеры:

Input: arr[] = {5, 8}, K = 1, C = 1
Output: 8.0
Explanation: There is no need to perform any operations. The finally array will be {8, 5} Hence 8.0 is the maximum achievable value.

Input: arr[] = {5, 9}, K = 3, C = 1
Output: 4.5
Explanation: The value 9 can be splitted as 4.5 and 4.5. The final array will be {5, 4.5, 4.5} where the 3rd value is 4.5 which is maximum achievable.

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

  • Инициализируйте две переменные, скажем, low и high как 0 и 10 9 соответственно, которые представляют диапазон, в котором может выполняться двоичный поиск.
  • Выполните двоичный поиск, используя следующие шаги:
    • Найдите значение mid как (low + high)*0.5 .
    • Пройдите по заданному массиву arr[] и сохраните количество элементов, которое равно как минимум значению mid в переменной, скажем, A , а также найдите количество операций, выполненных в переменной, скажем, B .
    • Если значение (A ≥ K) и (B + C ≥ K) , то обновить значение low как mid . В противном случае обновите значение high как mid .
  • После выполнения вышеуказанных шагов значение, сохраненное в переменной low , является результирующим максимизированным K -м максимальным элементом.

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

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

РЕКОМЕНДУЕМЫЕ СТАТЬИ