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

Опубликовано: 25 Февраля, 2023

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

  • За одну операцию можно выбрать любой элемент данного arr[] и заменить его соседним элементом.

Примеры:

Input: N = 7, K = 4, arr[] = {9, 7, 3, 5, 7, 8, 7}
Output: 7
Explanation: First operation: Change 3 at index 2 with 7 at index 1. 
So the arr[] becomes: {9, 7, 7, 5, 7, 8, 7}
Second Operation: Change 5 at index 3 with 7 at index 2.
So the arr[] becomes: {9, 7, 7, 7, 7, 8, 7} 
Third operation: Change 7 at index 6 with 8 at index 5.
So the arr[] becomes: {9, 7, 7, 7, 7, 8, 8}
Fourth Operation: Change 7 at index 1 with 9 at index 0.
So the arr[] becomes: {9, 9, 7, 7, 7, 8, 8}
The minimum value in arr[] after applying operation at most K times is: 7

Input: N = 4, K = 2, arr[] = {2, 5, 6, 8}
Output: 6
Explanation: First operation: Change 5 at index 1 with 6 at index 2.
So that the arr[] becomes: {2, 6, 6, 8}
Second operation: Change 2 at index 0 with 6 at index 1.
So that the arr[] becomes: {6, 6, 6, 8}
The minimum value of arr[] can be achieved by applying operations is: 6

Подход: Чтобы решить проблему, следуйте следующей идее:

Sort the arr[], if K is greater than or equal to length of arr[], simply return element at last index of arr[] else return element at Kth index of arr[]. 

Иллюстрация с примером:

Consider N = 6, K = 3, arr[] = {9, 7, 3, 1, 2, 5}

We can perform the following operations

Operation 1:- Change 2 at index 4 with 5 at index 5 . So the arr[] becomes: {9, 7, 3, 1, 5, 5}
Operation 2:- Change 1 at index 3 with 5 at index 4 . So the arr[] becomes: {9, 7, 3, 5, 5, 5}
Operation 3:- Change 3 at index 2 with 7 at index 1 . So the arr[] becomes: {9, 7, 7, 5, 5, 5}
Minimum element after applying operation at most 3 times is:  5

When you will sort the arr[] and return arr[K] you will get the same output :-

Sorted arr[]: {1, 2, 3, 5, 7, 9}

arr[K] = arr[3] = 5, which is out required answer.  

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

  • Отсортируйте массив.
  • Проверьте, больше ли K или равно arr[] или нет.
    • Если да, то просто верните элемент по последнему индексу arr[].
    • В противном случае вернуть элемент с K -м индексом arr[].
  • Распечатайте вывод.

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

Временная сложность: O(N * logN), потому что выполняется сортировка.
Вспомогательное пространство: O(1), так как дополнительное пространство не требуется.

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