Dados dos arreglos W[] y L[] que consisten en N enteros positivos, donde W[i] se ubica inicialmente en la posición i en una recta numérica infinita. En cada salto hacia adelante, W[i] puede saltar a la posición (j + L[i]) desde su posición actual j a cualquier posición vacante. La tarea es encontrar el número mínimo de saltos hacia adelante necesarios para ordenar la array .
Ejemplos:
Entrada: W[] = {2, 1, 4, 3}, L[] = {4, 1, 2, 4}
Salida: 5
Explicación:
Inicialmente, 2 está en la posición 0, 1 está en la posición 1, 4 es en la posición 2, 3 está en la posición 3 en la recta numérica como: 2 1 4 3
Presione el número 2 para saltar de su posición actual 0 a la posición 4, disposición en la recta numérica: _ 1 4 3 2
Presione el número 3 para saltar desde su posición actual 3 a la posición 7, disposición en la recta numérica: _ 1 4 _ 2 _ _ 3
Presione el número 4 para saltar de su posición actual 2 a la posición 8, disposición en la recta numérica: _ 1 _ _ 2 _ _ 3 4Por lo tanto, el número total de saltos necesarios es 1 + 1 + 3 = 5.
Entrada: W[] = {3, 1, 2}, L[] = {1, 4, 5}
Salida: 3
Enfoque: el problema dado se puede resolver utilizando el enfoque codicioso al minimizar la cantidad de saltos necesarios para el elemento más pequeño de la array que no está correctamente posicionado en cada operación y actualizar la cantidad de saltos. Siga los pasos a continuación para resolver el problema:
Enfoque: el problema dado se puede resolver utilizando el enfoque codicioso al minimizar la cantidad de saltos necesarios para el elemento más pequeño de la array que no está correctamente posicionado en cada operación y actualizar la cantidad de saltos. Siga los pasos a continuación para resolver el problema:
- Inicialice una variable, digamos ans como 0 para almacenar el número mínimo de saltos necesarios.
- Cree una copia de la array W[] y almacene los elementos ordenados en la array arr[] .
- Inicializa un HashMap pos que almacena la posición actual del elemento W[i] .
- Recorra la array W[] y actualice la posición de W[i] en pos .
- Recorra la array arr[] en el rango [1, N – 1] y realice los siguientes pasos:
- Almacene la posición de arr[i] y la posición de arr[i – 1] en la array W[] en las variables, digamos curr y prev respectivamente.
- Si el valor de curr es mayor que prev , continúe con la siguiente iteración.
- De lo contrario, itere hasta que curr ≤ prev o curr ya esté ocupado e incremente el valor de curr por el salto e incremente el valor de ans por 1 .
- Actualice la posición de arr[i] en HashMap pos a curr .
- Después de completar los pasos anteriores, imprima el valor de ans como resultado.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the minimum number
// of jumps required to sort the array
void minJumps(int w[], int l[], int n)
{
// Base Case
if (n == 1) {
cout << 0;
return;
}
// Store the required result
int ans = 0;
// Stores the current position of
// elements and their respective
// maximum jump
unordered_map<int, int> pos, jump;
// Used to check if a position is
// already taken by another element
unordered_map<int, bool> filled;
// Stores the sorted array a[]
int a[n];
// Traverse the array w[] & update
// positions jumps array a[]
for (int i = 0; i < n; i++) {
pos[w[i]] = i;
filled[i] = true;
jump[w[i]] = l[i];
a[i] = w[i];
}
// Sort the array a[]
sort(a, a + n);
// Traverse the array a[] over
// the range [1, N-1]
for (int curr = 1;
curr < n; curr++) {
// Store the index of current
// element and its just smaller
// element in array w[]
int currElementPos
= pos[a[curr]];
int prevElementPos
= pos[a[curr - 1]];
if (currElementPos
> prevElementPos)
continue;
// Iterate until current element
// position is at most its just
// smaller element position
while (currElementPos
<= prevElementPos
|| filled[currElementPos]) {
currElementPos += jump[a[curr]];
ans++;
}
// Update the position of the
// current element
pos[a[curr]] = currElementPos;
filled[currElementPos] = true;
}
// Print the result
cout << ans;
}
// Driver Code
int main()
{
int W[] = { 2, 1, 4, 3 };
int L[] = { 4, 1, 2, 4 };
int N = sizeof(W) / sizeof(W[0]);
minJumps(W, L, N);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG {
// Function to find the minimum number
// of jumps required to sort the array
static void minJumps(int[] w, int[] l, int n)
{
// Base Case
if (n == 1) {
System.out.print(0);
return;
}
// Store the required result
int ans = 0;
// Stores the current position of
// elements and their respective
// maximum jump
HashMap<Integer, Integer> pos
= new HashMap<Integer, Integer>();
HashMap<Integer, Integer> jump
= new HashMap<Integer, Integer>();
// Used to check if a position is
// already taken by another element
HashMap<Integer, Boolean> filled
= new HashMap<Integer, Boolean>();
// Stores the sorted array a[]
int[] a = new int[n];
// Traverse the array w[] & update
// positions jumps array a[]
for (int i = 0; i < n; i++) {
if (pos.containsKey(w[i]))
pos.put(w[i], i);
else
pos.put(w[i], i);
if (filled.containsKey(w[i]))
filled.put(i, true);
else
filled.put(i, true);
if (jump.containsKey(w[i]))
jump.put(w[i], l[i]);
else
jump.put(w[i], l[i]);
a[i] = w[i];
}
// Sort the array a[]
Arrays.sort(a);
// Traverse the array a[] over
// the range [1, N-1]
for (int curr = 1; curr < n; curr++) {
// Store the index of current
// element and its just smaller
// element in array w[]
int currElementPos = pos.get(a[curr]);
int prevElementPos = pos.get(a[curr - 1]);
if (currElementPos > prevElementPos)
continue;
// Iterate until current element
// position is at most its just
// smaller element position
while (currElementPos <= prevElementPos
|| filled.containsKey(currElementPos)
&& filled.containsKey(
currElementPos)) {
currElementPos += jump.get(a[curr]);
ans++;
}
// Update the position of the
// current element
if (pos.containsKey(a[curr]))
pos.put(a[curr], currElementPos);
else
pos.put(a[curr], currElementPos);
if (filled.containsKey(currElementPos))
filled.put(currElementPos, true);
else
filled.put(currElementPos, true);
}
// Print the result
System.out.print(ans);
}
// Driver Code
public static void main(String[] args)
{
int[] W = { 2, 1, 4, 3 };
int[] L = { 4, 1, 2, 4 };
int N = W.length;
minJumps(W, L, N);
}
}
// This code is contributed by ukasp.
Python3
# Python3 program for the above approach
# Function to find the minimum number
# of jumps required to sort the array
def minJumps(w, l, n):
# Base Case
if (n == 1):
print(0)
return
# Store the required result
ans = 0
# Stores the current position of
# elements and their respective
# maximum jump
pos = {}
jump = {}
# Used to check if a position is
# already taken by another element
filled = {}
# Stores the sorted array a[]
a = [0 for i in range(n)]
# Traverse the array w[] & update
# positions jumps array a[]
for i in range(n):
pos[w[i]] = i
filled[i] = True
jump[w[i]] = l[i]
a[i] = w[i]
# Sort the array a[]
a.sort()
# Traverse the array a[] over
# the range [1, N-1]
for curr in range(1, n, 1):
# Store the index of current
# element and its just smaller
# element in array w[]
currElementPos = pos[a[curr]]
prevElementPos = pos[a[curr - 1]]
if (currElementPos > prevElementPos):
continue
# Iterate until current element
# position is at most its just
# smaller element position
while (currElementPos <= prevElementPos or
(currElementPos in filled and
filled[currElementPos])):
currElementPos += jump[a[curr]]
ans += 1
# Update the position of the
# current element
pos[a[curr]] = currElementPos
filled[currElementPos] = True
# Print the result
print(ans)
# Driver Code
if __name__ == '__main__':
W = [ 2, 1, 4, 3 ]
L = [ 4, 1, 2, 4 ]
N = len(W)
minJumps(W, L, N)
# This code is contributed by SURENDRA_GANGWAR
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to find the minimum number
// of jumps required to sort the array
static void minJumps(int []w, int []l, int n)
{
// Base Case
if (n == 1)
{
Console.Write(0);
return;
}
// Store the required result
int ans = 0;
// Stores the current position of
// elements and their respective
// maximum jump
Dictionary<int,
int> pos = new Dictionary<int,
int>();
Dictionary<int,
int> jump = new Dictionary<int,
int>();
// Used to check if a position is
// already taken by another element
Dictionary<int,
bool> filled = new Dictionary<int,
bool>();
// Stores the sorted array a[]
int []a = new int[n];
// Traverse the array w[] & update
// positions jumps array a[]
for(int i = 0; i < n; i++)
{
if (pos.ContainsKey(w[i]))
pos[w[i]] = i;
else
pos.Add(w[i], i);
if (filled.ContainsKey(w[i]))
filled[i] = true;
else
filled.Add(i, true);
if (jump.ContainsKey(w[i]))
jump[w[i]] = l[i];
else
jump.Add(w[i], l[i]);
a[i] = w[i];
}
// Sort the array a[]
Array.Sort(a);
// Traverse the array a[] over
// the range [1, N-1]
for(int curr = 1; curr < n; curr++)
{
// Store the index of current
// element and its just smaller
// element in array w[]
int currElementPos = pos[a[curr]];
int prevElementPos = pos[a[curr - 1]];
if (currElementPos > prevElementPos)
continue;
// Iterate until current element
// position is at most its just
// smaller element position
while (currElementPos <= prevElementPos ||
filled.ContainsKey(currElementPos) &&
filled[currElementPos])
{
currElementPos += jump[a[curr]];
ans++;
}
// Update the position of the
// current element
if (pos.ContainsKey(a[curr]))
pos[a[curr]] = currElementPos;
else
pos.Add(a[curr], currElementPos);
if (filled.ContainsKey(currElementPos))
filled[currElementPos] = true;
else
filled.Add(currElementPos, true);
}
// Print the result
Console.Write(ans);
}
// Driver Code
public static void Main()
{
int []W = { 2, 1, 4, 3 };
int []L = { 4, 1, 2, 4 };
int N = W.Length;
minJumps(W, L, N);
}
}
// This code is contributed by ipg2016107
Javascript
<script>
// Javascript program for the above approach
// Function to find the minimum number
// of jumps required to sort the array
function minJumps(w, l, n)
{
// Base Case
if (n == 1)
{
document.write(0);
return;
}
// Store the required result
var ans = 0;
var i;
// Stores the current position of
// elements and their respective
// maximum jump
var pos = new Map();
var jump = new Map();
// Used to check if a position is
// already taken by another element
var filled = new Map();
// Stores the sorted array a[]
var a = new Array(n);
// Traverse the array w[] & update
// positions jumps array a[]
for(i = 0; i < n; i++)
{
pos.set(w[i], i);
filled.set(i, true);
jump.set(w[i], l[i]);
a[i] = w[i];
}
// Sort the array a[]
a = a.sort(function(p, q)
{
return p - q;
});
// Traverse the array a[] over
// the range [1, N-1]
for(curr = 1; curr < n; curr++)
{
// Store the index of current
// element and its just smaller
// element in array w[]
var currElementPos = pos.get(a[curr]);
var prevElementPos = pos.get(a[curr - 1]);
if (currElementPos > prevElementPos)
continue;
// Iterate until current element
// position is at most its just
// smaller element position
while (currElementPos <= prevElementPos ||
filled[currElementPos])
{
currElementPos += jump.get(a[curr]);
ans += 1;
}
// Update the position of the
// current element
pos.set(a[curr], currElementPos);
filled.set(currElementPos, true);
}
// Print the result
document.write(ans);
}
// Driver Code
var W = [ 2, 1, 4, 3 ];
var L = [ 4, 1, 2, 4 ];
var N = W.length;
minJumps(W, L, N);
// This code is contributed by ipg2016107
</script>
Producción:
5
Complejidad de tiempo: O(N*log N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por shreyajaiswal3 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA