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

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

Примеры:

Input: A[] = {4, 2, 1, 5, 3}, K = 3, N = 5
Output: 2
Explanation: Select consecutive elements from index 1 to 3 and replace with the minimum of {4, 2, 1}. Therefore, A[] becomes {1, 1, 1, 5, 3}.
Select consecutive elements from index from 3 to 5 and replace with minimum of {1, 5, 3}. Therefore, A becomes {1, 1, 1, 1, 1}.
Therefore, the total number of operations required are 2.

Input: A[] = {3, 6, 2, 1, 4, 5}, K = 2, N=6
Output: 5
Explanation: Select consecutive elements from index 4 to 5 and replace with the minimum of {1, 4} is 1. Therefore, A[] becomes {3, 6, 2, 1, 1, 5}
Select consecutive elements from index 5 to 6 and replace with the minimum of {1, 5} is 1. Therefore, A[] becomes {3, 6, 2, 1, 1, 1}
Select consecutive elements from index 3 to 4 and replace with the minimum of {2, 1} is 1. Therefore, A[] becomes {3, 6, 1, 1, 1, 1}
Select consecutive elements from index 2 to 3 and replace with the minimum of {6, 1} is 1. Therefore, A[] becomes {3, 1, 1, 1, 1, 1}
Select consecutive elements from index 1 to 2 and replace with the minimum of {3, 1} is 1. Therefore, A[] becomes {1, 1, 1, 1, 1, 1}
Therefore, the total number of operations are 5.

Подход: Идея основана на следующих наблюдениях:

• Перестановка значения не имеет. Это то же самое, что поставить минимум в начале.
• Оптимальное количество необходимых операций можно рассчитать, начав с минимального индекса и продвигаясь вперед на K .

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

• Инициализируйте переменные i и count как 0 для повторения и подсчета минимального количества операций соответственно.
• Цикл while i меньше N – 1 , потому что, когда i достигает N – 1 , все элементы становятся равными. В каждой текущей итерации выполните следующие шаги:
  • Увеличьте счетчик на 1 .
  • Увеличьте i на K-1 , потому что самый правый обновленный элемент будет снова использоваться для следующего сегмента.
• Выведите значение count в качестве результата.

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

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