Ordenar la recta numérica dada como Array moviendo un elemento en i-ésimo índice por i pasos a la derecha

Dada una array arr[] de N enteros, la tarea es encontrar el número mínimo de movimientos necesarios para clasificar la array en orden ascendente moviendo un elemento en el i ^-ésimo índice i pasos hacia la derecha en un solo movimiento.

Nota: En un paso, dos números pueden estar en la misma posición.

Ejemplos:

Entrada: N = 4, arr[] = {1, 2, 7, 4}
Salida: 1
Explicación:  Mover el elemento en el índice 3 2 pasos a la derecha ordena la array en orden ascendente en 1 movimiento. Por lo tanto, imprima 1.

Entrada: N = 5, arr[] = {2, 5, 8, 1, 9}
Salida: 12
Explicación:
La forma más óptima de organizar la array es: arr[] = {-, -, -, 1, – , -, -,2, -, -, -, -, -, -, -, 5, -, -, -, -, -, -, -, 8, -, -, -, -, -, – , -, -, -, -, -, -,-, -, -, 20}

1. Primero arr[0] salta al índice 2, luego al índice 4 y luego al índice 7. Por lo tanto, Shifting arr[0] necesitará 3 movimientos para alcanzar el índice 7. 
2. Primero arr[1] salta al índice 3, luego al índice 7 y luego al índice 15. Por lo tanto, Shifting arr[1] necesitará 3 movimientos para alcanzar el índice 15. 
3. Primero arr[2] salta al índice 6, luego al índice 12 y luego al índice 24. Por lo tanto, Shifting arr[2] necesitará 3 movimientos para alcanzar el índice 23.
4. Primero arr[4] salta al índice 9, luego al índice 19 y luego al índice 39. Por lo tanto, Shifting arr[4] también necesitará 3 movimientos para alcanzar el índice 39.

Por lo tanto, se necesita el total de (3 + 3 + 3 + 3) = 12 movimientos.

Enfoque: El problema dado se puede resolver utilizando el Enfoque codicioso que se basa en las observaciones de que siempre es óptimo comenzar colocando el número más pequeño primero en su posición adecuada y luego colocar el elemento más grande en consecuencia. Siga los pasos a continuación para resolver el problema:

• Inicialice un mapa , digamos M , que almacene los elementos de la array con su índice en la array dada arr[] .
• Recorra la array dada arr[] usando la variable i y actualice el mapa M[arr[i]] como M[arr[i]] = (i + 1) .
• Inicialice una variable, digamos ans como 0 que almacene el número mínimo de movimientos totales requeridos.
• Recorra el mapa M y realice los siguientes pasos:
  • Almacene la posición del iterador actual y el iterador anterior en las variables i y j .
  • Iterar hasta que i->segundo sea menor o igual a j->segundo e incrementar el valor de ans en 1 e incrementar el valor de i->segundo en i->segundo .
• Después de completar los pasos anteriores, imprima el valor de ans como los movimientos mínimos resultantes.

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the minimum number
// of moves required to sort the numbers
int MinimumMoves(int arr[], int N)
{
    // Stores value of number and the
    // position of the number
    map<int, int> mp;
 
    for (int i = 0; i < N; i++) {
       
        // Update mp[arr[i]]
        mp[arr[i]] = (i + 1);
    }
 
    // Stores the iterator pointing at
      // the beginning of the map
    auto it = mp.begin();
    it++;
 
    // Stores the minimum count of moves
    int ans = 0;
 
    // Traverse the map mp
    for (auto i = it; i != mp.end(); i++) {
       
        // Stores previous iterator
        auto j = i;
        j--;
 
        // Iterate while i->second is less
          // than or equal to j->second
        while (i->second <= j->second) {
 
            // Update the i->second
            i->second += i->second;
           
            // Increment ans by 1
            ans++;
        }
    }
   
    // Return the resultant minimum moves
    return ans;
}
 
// Driver Code
int main()
{
    int arr[] = { 2, 5, 8, 1, 9 };
    int N = sizeof(arr) / sizeof(arr[0]);
    cout << MinimumMoves(arr, N);
   
      return 0;
}

// Java program for the above approach
import java.io.*;
import java.util.*;
 
class GFG {
 
    // Function to find the minimum number
    // of moves required to sort the numbers
    static int MinimumMoves(int arr[], int N)
    {
       
        // Stores value of number and the
        // position of the number
        Map<Integer, Integer> mp
            = new HashMap<Integer, Integer>();
 
        for (int i = 0; i < N; i++) {
 
            // Update mp[arr[i]]
            if (mp.containsKey(arr[i])) {
 
                mp.put(arr[i], mp.get(arr[i]) + (i + 1));
            }
            else {
 
                mp.put(arr[i], (i + 1));
            }
        }
 
        // Stores the iterator pointing at
        // the beginning of the map
        Iterator<Map.Entry<Integer, Integer> > it
            = mp.entrySet().iterator();
 
        Map.Entry<Integer, Integer> i = it.next();
       
        // Stores the minimum count of moves
        int ans = 0;
 
        // Traverse the map mp
        while (it.hasNext()) {
 
            // Stores previous iterator
            Map.Entry<Integer, Integer> j = i;
            i = it.next();
 
            // Iterate while i->second is less
            // than or equal to j->second
            while (i.getValue() <= j.getValue()) {
 
                // Update the i->second
                i.setValue(i.getValue() + i.getValue());
 
                // Increment ans by 1
                ans++;
            }
        }
 
        // Return the resultant minimum moves
        return ans;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int arr[] = { 2, 5, 8, 1, 9 };
        int N = arr.length;
        System.out.println(MinimumMoves(arr, N));
    }
}
 
// This code is contributed by Dharanendra L V.

12

Complejidad de tiempo: O(N*log N)
Espacio auxiliar: O(N)