Número mínimo de saltos requeridos para ordenar la array dada en orden ascendente

Dadas dos arrays arr[] y jump[] , cada una de longitud N , donde jump[i] denota el número de índices por los que 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 .

Nota: 
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 se pueden mover 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 problema dado se puede resolver con avidez . Siga los pasos a continuación para resolver el problema:

• Inicialice una variable, digamos jumps = 0 , para almacenar el número mínimo de saltos necesarios.
• Inicialice una array, digamos temp[] , donde temp[arr[i]] almacena la distancia que puede saltar arr[i]
• Inicialice un vector de pares , digamos vect , para almacenar los elementos de la array arr[] y sus respectivos índices, es decir , {arr[i], i + 1}
• Ordenar el vector vector .
• Atraviese el vector vect , sobre el rango de índices [1, N – 1]. Actualice el valor de vect[i] mientras vect[i].segundo ≤ vect[i-1].segundo , agregando la distancia de salto a vect[i].segundo .
• Incrementa los saltos en 1 .
• Imprime el valor de los saltos .

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 count minimum number
// of jumps required to sort the array
void minJumps(int arr[], int jump[], int N)
{
    // Stores minimum number of jumps
    int jumps = 0;
 
    // Stores distances of jumps
    int temp[1000];
 
    // Stores the array elements
    // with their starting indices
    vector<pair<int, int> > vect;
 
    // Push the pairs {arr[i], i+1}
    // into the vector of pairs vect
    for (int i = 0; i < N; i++) {
 
        // Update vect
        vect.push_back({ arr[i], i + 1 });
    }
 
    // Populate the array temp[]
    for (int i = 0; i < N; i++) {
 
        // Update temp[arr[i]]
        temp[arr[i]] = jump[i];
    }
 
    // Sort the vector in
    // the ascending order
    sort(vect.begin(), vect.end());
 
    for (int i = 1; i < N; i++) {
        // Jump till the previous
        // index <= current index
        while (vect[i].second <= vect[i - 1].second) {
            // Update vect[i]
            vect[i] = make_pair(vect[i].first,
                                vect[i].second
                                    + temp[vect[i].first]);
 
            // Increment the
            // number of jumps
            jumps++;
        }
    }
 
    // Print the minimum number
    // of jumps required
    cout << jumps << endl;
}
 
// Driver Code
int main()
{
    // Input
    int arr[] = { 3, 2, 1 };
    int jump[] = { 1, 1, 1 };
 
    // Size of the array
    int N = sizeof(arr) / sizeof(arr[0]);
 
    minJumps(arr, jump, N);
 
    return 0;
}

// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
 
class GFG{
 
// Function to count minimum number
// of jumps required to sort the array
static void minJumps(int arr[], int jump[], int N)
{
     
    // Stores minimum number of jumps
    int jumps = 0;
 
    // Stores distances of jumps
    int temp[] = new int[1000];
 
    // Stores the array elements
    // with their starting indices
    int vect[][] = new int[N][2];
 
    // Push the pairs {arr[i], i+1}
    // into the vector of pairs vect
    for(int i = 0; i < N; i++)
    {
         
        // Update vect
        vect[i][0] = arr[i];
        vect[i][1] = i + 1;
    }
 
    // Populate the array temp[]
    for(int i = 0; i < N; i++)
    {
         
        // Update temp[arr[i]]
        temp[arr[i]] = jump[i];
    }
 
    // Sort the vector in
    // the ascending order
    Arrays.sort(vect, (a, b) -> {
        if (a[0] != b[0])
            return a[0] - b[0];
             
        return a[1] - b[1];
    });
 
    for(int i = 1; i < N; i++)
    {
         
        // Jump till the previous
        // index <= current index
        while (vect[i][1] <= vect[i - 1][1])
        {
             
            // Update vect[i]
            vect[i][0] = vect[i][0];
            vect[i][1] = vect[i][1] + temp[vect[i][0]];
 
            // Increment the
            // number of jumps
            jumps++;
        }
    }
 
    // Print the minimum number
    // of jumps required
    System.out.println(jumps);
}
 
// Driver Code
public static void main(String[] args)
{
     
    // Input
    int arr[] = { 3, 2, 1 };
    int jump[] = { 1, 1, 1 };
 
    // Size of the array
    int N = arr.length;
 
    minJumps(arr, jump, N);
}
}
 
// This code is contributed by Kingash

# Python3 program for the above approach
 
# Function to count minimum number
# of jumps required to sort the array
def minJumps(arr, jump, N):
     
    # Stores minimum number of jumps
    jumps = 0
 
    # Stores distances of jumps
    temp = [0 for i in range(1000)]
 
    # Stores the array elements
    # with their starting indices
    vect = []
     
    # Push the pairs {arr[i], i+1}
    # into the vector of pairs vect
    for i in range(N):
         
        # Update vect
        vect.append([arr[i], i + 1])
 
    # Populate the array temp[]
    for i in range(N):
         
        # Update temp[arr[i]]
        temp[arr[i]] = jump[i]
 
    # Sort the vector in
    # the ascending order
    vect.sort(reverse = False)
 
    for i in range(N):
         
        # Jump till the previous
        # index <= current index
        while (vect[i][1] <= vect[i - 1][1]):
             
            # Update vect[i]
            vect[i] = [vect[i][0], vect[i][1] +
                  temp[vect[i][0]]]
 
            # Increment the
            # number of jumps
            jumps += 1
 
    # Print the minimum number
    # of jumps required
    print(jumps)
 
# Driver Code
if __name__ == '__main__':
     
    # Input
    arr =  [3, 2, 1]
    jump = [1, 1, 1]
 
    # Size of the array
    N = len(arr)
 
    minJumps(arr, jump, N)
 
# This code is contributed by SURENDRA_GANGWAR

// C# program for the above approach
using System;
using System.Linq;
using System.Collections.Generic;
 
class GFG {
    public class pair {
    public int first, second;
  
    public pair(int first, int second) {
      this.first = first;
      this.second = second;
    }
  }
      
// Function to count minimum number
// of jumps required to sort the array
static void minJumps(int[] arr, int[] jump, int N)
{
    // Stores minimum number of jumps
    int jumps = 0;
  
    // Stores distances of jumps
    int[] temp= new int[1000];
  
    // Stores the array elements
    // with their starting indices
    List<pair> vect;
    vect = new List<pair>();
  
    // Push the pairs {arr[i], i+1}
    // into the vector of pairs vect
    for(int i = 0; i < N; i++)
    {
          
        // Update vect
        vect.Add(new pair(arr[i], i+1));
    }
  
    // Populate the array temp[]
    for (int i = 0; i < N; i++) {
  
        // Update temp[arr[i]]
        temp[arr[i]] = jump[i];
    }
     
    // Sort the vector in
    // the ascending order
    vect.Sort((a, b) => { if (a.first != b.first)
            return a.first - b.first;
              
        return a.second - b.second; });
         
  
    for(int i = 1; i < N; i++)
    {
          
        // Jump till the previous
        // index <= current index
        while (vect[i].second <= vect[i - 1].second)
        {
              
            // Update vect[i]
            vect[i].first = vect[i].first;
            vect[i].second = vect[i].second + temp[vect[i].first];
  
            // Increment the
            // number of jumps
            jumps++;
        }
    }
  
    // Print the minimum number
    // of jumps required
    Console.WriteLine(jumps);
}
  
    // Driver program
    public static void Main()
    {
        // Input
        int[] arr = new int[] { 3, 2, 1 };
        int[] jump = new int[] { 1, 1, 1 };
  
        // Size of the array
        int N = arr.Length;
  
        minJumps(arr, jump, N);
    }
}
 
// This code is contributed by Pushpesh Raj.

<script>
    // JavaScript program for the above approach
 
    // Function to count minimum number
    // of jumps required to sort the array
    const minJumps = (arr, jump, N) => {
     
        // Stores minimum number of jumps
        let jumps = 0;
 
        // Stores distances of jumps
        let temp = new Array(1000).fill(0);
 
        // Stores the array elements
        // with their starting indices
        let vect = [];
 
        // Push the pairs {arr[i], i+1}
        // into the vector of pairs vect
        for (let i = 0; i < N; i++) {
 
            // Update vect
            vect.push([arr[i], i + 1]);
        }
 
        // Populate the array temp[]
        for (let i = 0; i < N; i++) {
 
            // Update temp[arr[i]]
            temp[arr[i]] = jump[i];
        }
 
        // Sort the vector in
        // the ascending order
        vect.sort();
 
        for (let i = 1; i < N; i++) {
            // Jump till the previous
            // index <= current index
            while (vect[i][1] <= vect[i - 1][1]) {
                // Update vect[i]
                vect[i] = [vect[i][0],
                vect[i][1]
                + temp[vect[i][0]]];
 
                // Increment the
                // number of jumps
                jumps++;
            }
        }
 
        // Print the minimum number
        // of jumps required
        document.write(`${jumps}<br/>`);
    }
 
    // Driver Code
 
    // Input
    let arr = [3, 2, 1];
    let jump = [1, 1, 1];
 
    // Size of the array
    let N = arr.length;
 
    minJumps(arr, jump, N);
 
// This code is contributed by rakeshsahni
 
</script>

6

Tiempo Complejidad: O(N ² )
Espacio Auxiliar: O(N)