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

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

• Выберите префикс размера K , где arr[K] = максимальный элемент в этом выбранном подмассиве, и преобразуйте все элементы, равные max.
• Выберите любой подмассив и один раз поверните его влево.

Примеры:

Input: N = 2, arr[] = {34, 34}
Output: 0
Explanation: All the elements are equal already. Therefore, No need to apply operations on it, Hence cost is zero.

Input: N = 3, arr[] = {1, 2, 3}
Output: 1
Explanation: 
First operation: Choose prefix sub-array {A1, A2, A3} in which arr[3] = max element in sub-array and equal all the elements with max = {3, 3, 3}. Therefore, minimum cost is 1. 

Подход: Задача может быть решена на основе следующего наблюдения:

We can solve any case at most 2 operations. For more clarification see the concept of approach and its illustration below.

If the max element is present at last index of the arr[], Then all the elements can be make equal by using the first operation only. From this we can conclude that the optimal choice is to place the maximum element of the array at the last index. We can shift max element to the last index using only one instance of second operation.

So there are three cases:

• If max = min in arr[], Then arr[] elements are equal already. Therefore, minimum cost is 0. 
• If max element is present at last index of arr[], Then elements can be make equal by applying First operation. Therefore, minimum cost is is 1. 
• Rest of the cases except above two will take two operations. Therefore, minimum cost is 2.

Для реализации идеи выполните следующие шаги:

• Создайте переменные max, min и max_index для хранения максимального, минимального элемента и индекса максимального элемента соответственно.
• Затем проверьте следующие условия:
  • Если max = min, тогда минимальная стоимость равна 0.
  • Если max_index = N , тогда минимальная стоимость равна 1.
  • В остальных случаях будет минимальная стоимость равна 2.

Ниже приведена реализация описанного выше подхода.

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

Статьи по Теме:

• Введение в массивы - учебные пособия по структурам данных и алгоритмам
• Введение в жадные алгоритмы - учебные пособия по структурам данных и алгоритмам