Dados dos arreglos A[] y B[] que consisten en N enteros positivos tales que cada elemento del arreglo A[i] se coloca en la i -ésima posición en la recta numérica, la tarea es encontrar el número mínimo de operaciones requeridas para ordenar el elementos de array dispuestos en la recta numérica. En cada operación, cualquier elemento del arreglo A[i] puede moverse a la posición (i + B[i]) en la recta numérica. Dos o más elementos pueden venir a la misma recta numérica.
Ejemplos:
Entrada: A[] = {2, 1, 4, 3}, B[] = {4, 1, 2, 4}
Salida: 5
Explicación:
Inicialmente, las arrays 2, 1, 4, 3 se colocan en la recta numérica en las posiciones 0, 1, 2, 3 respectivamente.
Operación 1: Mover arr[0](= 2) por move[0](= 4). Ahora los elementos están dispuestos como {1, 4, 3, 2} en los índices de la recta numérica {1, 2, 3, 4} respectivamente.
Operación 2: Mover arr[3](= 3) por move[3](= 4). Ahora los elementos están dispuestos como {1, 4, 2, 3} en los índices de la recta numérica {1, 2, 4, 7} respectivamente.
Operación 3: Mover arr[2](= 4) mover[2](= 2). Ahora los elementos están dispuestos como {1, 2, 4, 3} en los índices de la recta numérica {1, 4, 4, 7} respectivamente.
Operación 4: Mover arr[3](= 4)mover[2](= 2). Ahora los elementos están dispuestos como {1, 2, 3, 4} en los índices de la recta numérica {1, 4, 6, 7} respectivamente.
Operación 5: En la primera operación mueva arr[0](= 2) es decir, 2 por move[0](= 4). Ahora los elementos están dispuestos como {1, 4, 3, 2} en los índices de la recta numérica {1, 4, 7, 8} respectivamente.Entrada: A[] = {1, 2, 3, 4}, B[] = {4, 1, 2, 4}
Salida: 0
Enfoque: El problema dado se puede resolver usando el Enfoque codicioso moviendo el elemento mayor uno por uno a su siguiente índice posible y luego encuentre el mínimo de todas las operaciones requeridas. Siga los pasos a continuación para resolver el problema dado:
- Inicialice vectores 2D , digamos arr[] de modo que cada i -ésimo elemento represente el elemento, los movimientos correspondientes y la posición actual como {arr[i], A[i], current_position} .
- Ordene la array arr[] en orden ascendente .
- Inicialice dos variables, digamos cnt y f , y marque el conteo como 0 y marque como 1 para almacenar el número de operaciones requeridas.
- Iterar hasta que F no sea igual a 1 y realizar los siguientes pasos:
- Actualizar el valor de F es igual a 0 .
- Para cada elemento en el vector arr[] y Si el valor de arr[i][2] es al menos arr[i + 1][2] , entonces incremente el conteo en 1 , f = 1 y la posición actual del ( i + 1) el elemento es decir, (arr[i + 1][2]) por arr[i + 1][1] .
- Después de completar los pasos anteriores, imprima el valor de conteo 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 minimum number of
// operations required to sort N array
// elements placed on a number line
int minHits(int arr[], int move[],
int n)
{
// Stores the value of
// {A[i], B[i], current position}
vector<vector<int> > V(n, vector<int>(3));
// Populate the current position
// every elements
for (int i = 0; i < n; i++) {
V[i] = { arr[i], move[i], i };
}
// Sort the vector V
sort(V.begin(), V.end());
// Stores the total number of
// operations required
int cnt = 0;
int f = 1;
// Iterate until f equals 1
while (f == 1) {
// Update f equals zero
f = 0;
// Traverse through vector
// and check for i and i+1
for (int i = 0; i < n - 1; i++) {
// If current position of
// i is at least current
// position of i+1
if (V[i][2] >= V[i + 1][2]) {
// Increase the current
// position of V[i+1][2]
// by V[i+1][1]
V[i + 1][2] += V[i + 1][1];
// Increment the count
// of operations
cnt++;
// Update the flag equals
// to 1
f = 1;
// Break the for loop
break;
}
}
}
// Return the total operations
// required
return cnt;
}
// Driver Code
int main()
{
int A[] = { 2, 1, 4, 3 };
int B[] = { 4, 1, 2, 4 };
int N = sizeof(A) / sizeof(A[0]);
cout << minHits(A, B, N);
return 0;
}
Python3
# python 3 program for the above approach
# Function to find minimum number of
# operations required to sort N array
# elements placed on a number line
def minHits(arr, move, n):
# Stores the value of
# {A[i], B[i], current position}
temp = [0 for i in range(3)]
V = [temp for i in range(n)]
# Populate the current position
# every elements
for i in range(n):
V[i] = [arr[i], move[i], i]
# Sort the vector V
V.sort()
# Stores the total number of
# operations required
cnt = 0
f = 1
# Iterate until f equals 1
while(f == 1):
# Update f equals zero
f = 0
# Traverse through vector
# and check for i and i+1
for i in range(n - 1):
# If current position of
# i is at least current
# position of i+1
if (V[i][2] >= V[i + 1][2]):
# Increase the current
# position of V[i+1][2]
# by V[i+1][1]
V[i + 1][2] += V[i + 1][1]
# Increment the count
# of operations
cnt += 1
# Update the flag equals
# to 1
f = 1
# Break the for loop
break
# Return the total operations
# required
return cnt
# Driver Code
if __name__ == '__main__':
A = [2, 1, 4, 3]
B = [4, 1, 2, 4]
N = len(A)
print(minHits(A, B, N))
# This code is contributed by bgangwar59.
Javascript
<script>
// JavaScript program for the above approach
// Function to find minimum number of
// operations required to sort N array
// elements placed on a number line
function minHits(arr, move, n) {
// Stores the value of
// {A[i], B[i], current position}
let V = new Array(n).fill(0).map(() => new Array(3));
// Populate the current position
// every elements
for (let i = 0; i < n; i++) {
V[i] = [arr[i], move[i], i];
}
// Sort the vector V
V.sort((a, b) => a[0] - b[0]);
// Stores the total number of
// operations required
let cnt = 0;
let f = 1;
// Iterate until f equals 1
while (f == 1) {
// Update f equals zero
f = 0;
// Traverse through vector
// and check for i and i+1
for (let i = 0; i < n - 1; i++) {
// If current position of
// i is at least current
// position of i+1
if (V[i][2] >= V[i + 1][2]) {
// Increase the current
// position of V[i+1][2]
// by V[i+1][1]
V[i + 1][2] += V[i + 1][1];
// Increment the count
// of operations
cnt++;
// Update the flag equals
// to 1
f = 1;
// Break the for loop
break;
}
}
}
// Return the total operations
// required
return cnt;
}
// Driver Code
let A = [2, 1, 4, 3];
let B = [4, 1, 2, 4];
let N = A.length;
document.write(minHits(A, B, N));
</script>
5
Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por vedantvalsangkar y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA