Максимизируйте минимальное значение массива, заменяя элементы с соседними K раз
Дан массив 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: 7Input: 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: 5When 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), так как дополнительное пространство не требуется.