Número mínimo de saltos requeridos para Ordenar el Array dado en orden ascendente| Conjunto-2

Dadas dos arrays arr[] y jump[] , cada una de longitud N , donde jump[i] denota el número de índices por los cuales el i ^-ésimo elemento en la array arr[] puede avanzar, la tarea es encontrar el número mínimo de saltos necesarios para que la array se ordene en orden ascendente .

• Todos los elementos de la array arr[] son ​​distintos.
• Al saltar, los elementos de la array pueden superponerse (es decir, estar en el mismo índice).
• Los elementos de la array pueden moverse a los índices que exceden el tamaño de la array

Ejemplos:

Entrada: arr[] = {3, 1, 2}, jump[ ] = {1, 4, 5}
Salida: 3
Explicación: La siguiente secuencia requiere un número mínimo de saltos para clasificar la array en orden ascendente:
Salto 1: arr[ 0] salta de 1 ( = jump[0]) índice a índice 1.
Jump 2: arr[0] salta de 1 ( = jump[0]) índice a índice 2.
Jump 3: arr[0] salta de 1 ( = saltar[0]) índice al índice 3.
Por lo tanto, el número mínimo de operaciones requeridas es 3.

Entrada: arr[] = {3, 2, 1}, jump[ ] = {1, 1, 1}
Salida: 6
Explicación: La siguiente secuencia requiere un número mínimo de saltos para clasificar la array en orden ascendente:
Salto 1: arr[ 0] salta de 1 ( = jump[0]) índice al índice 1.
Jump 2: arr[0] salta de 1 ( = jump[0]) índice al índice 2.
Jump 3: arr[0] salta de 1 ( = jump[0]) índice al índice 3.
Jump 4: arr[1] salta de 1 ( = jump[0]) índice al índice 2.
Jump 5: arr[1] salta de 1 ( = jump [0]) índice al índice 3.
Saltar 6: arr[0] salta de 1 ( = jump[0]) índice al índice 4.
Por lo tanto, el número mínimo de operaciones requeridas es 6 .

Enfoque: El enfoque ingenuo para la solución se menciona en el Conjunto-1 de este problema. Para determinar el número de saltos para cada elemento aquí se toma la ayuda del mapa . Para el elemento actual, determine el elemento anterior que estará allí en orden y luego determine el número de saltos necesarios para colocar el elemento actual después de ese. Siga los pasos que se mencionan a continuación:

• Almacena la posición actual de cada elemento en un mapa.
• Almacene los elementos ordenados en un conjunto.
• Encuentre la diferencia de posición del elemento actual con su elemento anterior en orden ordenado. Luego encuentre el número de saltos requeridos dividiendo la diferencia con la longitud del salto actual.
• Agregue este conteo a la respuesta final.
• Devuelve la respuesta final.

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 return minimum required jumps
int minJumps(
    vector<int> arr, vector<int> jump, int N)
{
    int temp[N];
    for (int i = 0; i < N; i++)
        temp[i] = arr[i];
    sort(temp, temp + N);
    unordered_map<int, int> a;
    for (int i = 0; i < N; i++)
    {
        a[arr[i]] = i;
    }
    int ans = 0;
    int x = 1, y = 0;
    while (x < N)
    {
        if (a[temp[x]] <= a[temp[y]])
        {
            int jumps = ceil((a[temp[y]] - a[temp[x]] + 1) / jump[a[temp[x]]]);
 
            ans += jumps;
            a[temp[x]] = a[temp[x]] + jumps * jump[a[temp[x]]];
        }
        x++;
        y++;
    }
    return ans;
}
 
// Driver code
int main()
{
    int N = 3;
    vector<int> arr = {3, 2, 1};
    vector<int> jump = {1, 1, 1};
 
    cout << (minJumps(arr, jump, N));
    return 0;
}
 
// This code is contributed by lokeshpotta20.

// Java code to implement the above approach
import java.io.*;
import java.util.*;
 
class GFG {
    // Function to return minimum required jumps
    public static int minJumps(
        int arr[], int jump[], int N)
    {
        int temp[] = new int[N];
        for (int i = 0; i < N; i++)
            temp[i] = arr[i];
        Arrays.sort(temp);
        HashMap<Integer, Integer> a = new HashMap<>();
        for (int i = 0; i < N; i++) {
            a.put(arr[i], i);
        }
        int ans = 0;
        int x = 1, y = 0;
        while (x < N) {
            if (a.get(temp[x]) <= a.get(temp[y])) {
                int jumps = (int)Math.ceil(
                    (float)(a.get(temp[y])
                            - a.get(temp[x])
                            + 1)
                    / jump[a.get(temp[x])]);
                ans += jumps;
                a.put(temp[x],
                      a.get(temp[x])
                          + jumps
                                * jump[a.get(temp[x])]);
            }
            x++;
            y++;
        }
        return ans;
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int N = 3;
        int arr[] = { 3, 2, 1 };
        int jump[] = { 1, 1, 1 };
 
        System.out.println(minJumps(arr, jump, N));
    }
}

# Python program for the above approach
import math as Math
 
# Function to return minimum required jumps
def minJumps(arr, jump, N):
    temp = [0] * N
    for i in range(N):
        temp[i] = arr[i]
    temp.sort()
    a = {}
    for i in range(N):
        a[arr[i]] = i
 
    ans = 0
    x = 1
    y = 0
    while x < N:
        if a[temp[x]] <= a[temp[y]]:
            jumps = Math.ceil((a[temp[y]] - a[temp[x]] + 1) / jump[a[temp[x]]])
 
            ans += jumps
            a[temp[x]] = a[temp[x]] + jumps * jump[a[temp[x]]]
        x += 1
        y += 1
    return ans
 
# Driver code
 
N = 3
arr = [3, 2, 1]
jump = [1, 1, 1]
 
print(minJumps(arr, jump, N))
 
# This code is contributed by Saurabh Jaiswal

// C# program for the above approach
using System;
using System.Collections.Generic;
 
class GFG{
     
// Function to return minimum required jumps
public static int minJumps(int[] arr, int[] jump, int N)
{
    int[] temp = new int[N];
    for(int i = 0; i < N; i++)
        temp[i] = arr[i];
         
    Array.Sort(temp);
    Dictionary<int, int> a = new Dictionary<int, int>();
     
    for(int i = 0; i < N; i++)
    {
        a[arr[i]] = i;
    }
     
    int ans = 0;
    int x = 1, y = 0;
    while (x < N)
    {
        if (a[temp[x]] <= a[temp[y]])
        {
            int jumps = (int)Math.Ceiling(
                (float)(a[temp[y]] - a[temp[x]] + 1) /
                   jump[a[temp[x]]]);
                    
            ans += jumps;
            a[temp[x]] = a[temp[x]] + jumps * jump[a[temp[x]]];
        }
        x++;
        y++;
    }
    return ans;
}
 
// Driver code
public static void Main(string[] args)
{
    int N = 3;
    int[] arr = { 3, 2, 1 };
    int[] jump = { 1, 1, 1 };
 
    Console.Write(minJumps(arr, jump, N));
}
}
 
// This code is contributed by ukasp

<script>
    // JavaScript program for the above approach
 
    // Function to return minimum required jumps
    const minJumps = (arr, jump, N) => {
        let temp = new Array(N).fill(0);
        for (let i = 0; i < N; i++)
            temp[i] = arr[i];
        temp.sort();
        let a = {};
        for (let i = 0; i < N; i++) {
            a[arr[i]] = i;
        }
        let ans = 0;
        let x = 1, y = 0;
        while (x < N) {
            if (a[temp[x]] <= a[temp[y]]) {
                let jumps = Math.ceil((a[temp[y]] - a[temp[x]] + 1) / jump[a[temp[x]]]);
 
                ans += jumps;
                a[temp[x]] = a[temp[x]] + jumps * jump[a[temp[x]]];
            }
            x++;
            y++;
        }
        return ans;
    }
 
    // Driver code
 
    let N = 3;
    let arr = [3, 2, 1];
    let jump = [1, 1, 1];
 
    document.write(minJumps(arr, jump, N));
 
// This code is contributed by rakeshsahni
 
</script>

6

Complejidad temporal: O(N * logN)
Espacio auxiliar: O(N)