Отсортировать элементы массива A[], расположенные на числовой строке, сдвигая i-й элемент на (i + B[i])-ю позицию минимальное количество раз

Даны два массива A[] и B[] , состоящие из N положительных целых чисел, такие, что каждый элемент массива A[i] стоит на i ^-й позиции числовой строки, задача состоит в том, чтобы найти минимальное количество операций, необходимых для сортировки элементы массива расположены в числовой строке. В каждой операции любой элемент массива A[i] может переместиться на позицию (i + B[i])- ^ю на числовой прямой. На одну и ту же числовую прямую могут прийти два и более элемента.

Примеры:

Input: A[] = {2, 1, 4, 3}, B[] = {4, 1, 2, 4}
Output: 5
Explanation:

Initially array 2, 1, 4, 3 are placed on the number line at 0, 1, 2, 3 positions respectively.
Operation 1: Move arr[0](= 2) by move[0](= 4). Now the element are arranged as {1, 4, 3, 2} at indices on the number line is {1, 2, 3, 4} respectively.
Operation 2: Move arr[3](= 3) by move[3](= 4). Now the element are arranged as {1, 4, 2, 3} at indices on the number line is {1, 2, 4, 7} respectively.
Operation 3: Move arr[2](= 4) move[2](= 2). Now the element are arranged as {1, 2, 4, 3} at indices on the number line is {1, 4, 4, 7} respectively.
Operation 4: Move arr[3](= 4) move[2](= 2). Now the element are arranged as {1, 2, 3, 4} at indices on the number line is {1, 4, 6, 7} respectively.
Operation 5: In first operation move arr[0](= 2) i.e., 2 by move[0](= 4). Now the element are arranged as {1, 4, 3, 2} at indices on the number line is {1, 4, 7, 8} respectively.

Input: A[] = {1, 2, 3, 4}, B[] = {4, 1, 2, 4}
Output: 0

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

• Инициализируйте 2D-векторы, скажем, arr[] таким образом, чтобы каждый i ^-й элемент представлял элемент, соответствующие перемещения и текущую позицию как {arr[i], A[i], current_position} .
• Отсортируйте массив arr[] по возрастанию.
• Инициализируйте две переменные, скажем, cnt и f , и пометьте count как 0 и пометьте как 1 , чтобы сохранить количество требуемых операций.
• Итерируйте до тех пор, пока F не станет равным 1 , и выполните следующие шаги:
  • Обновите значение F равным 0 .
  • Для каждого элемента в векторе arr[] и если значение arr[i][2] не меньше arr[i + 1][2] , то увеличиваем счетчик на 1 , f = 1 и текущую позицию ( i + 1) ^th элемент, т.е. (arr[i + 1][2]) на arr[i + 1][1] .
• После выполнения вышеуказанных шагов выведите в качестве результата значение count .

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

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