Dadas dos arrays A[] y B[] que consisten en M y N enteros respectivamente, y un entero C , la tarea es encontrar el costo mínimo requerido para hacer que la secuencia A sea exactamente igual a B (consiste solo en elementos distintos) por realizando las siguientes operaciones en la array A[] :
- Elimina cualquier elemento de la array con costo 0 .
- Inserte un nuevo elemento en cualquier lugar de la array con costo C .
Ejemplos:
Entrada: A[] = {1, 6, 3, 5, 10}, B[] = {3, 1, 5}, C = 2
Salida: 2
Explicación:
Eliminar los elementos 1, 6 y 10 de la array cuesta 0. La array A[] se convierte en {3, 5}.
Agregue 1 entre 3 y 5, luego la array arr[] se convierte en {3, 1, 5} que es lo mismo que la array B[].
El costo de la operación anterior es 2.Entrada: A[] = {10, 5, 2, 4, 10, 5}, B[] = {5, 1, 2, 10, 4}, C = 3
Salida: 6
Explicación:
Eliminación de elementos 10, 10, y 5 de la array cuesta 0. La array A[] se convierte en {5, 2, 4}.
Agregue los elementos 1 y 10 en la array como {5, 1, 2, 10, 4}, que es lo mismo que la array B[].
El costo de la operación anterior es 3*2 = 6.
Enfoque ingenuo: el enfoque más simple es borrar todos los elementos de la array A[] que no están presentes en la array B[] mediante el uso de dos bucles for. Después de eso , genere todas las permutaciones del elemento restante en la array y para cada secuencia verifique el costo mínimo de modo que la array A[] sea la misma que la array B[] . Imprimir el coste mínimo del mismo.
Complejidad de tiempo: O(N!*N*M), donde N es el tamaño de la array A[] y M es el tamaño de la array B[].
Espacio Auxiliar: O(1)
Enfoque eficiente: para optimizar el enfoque anterior, la idea es encontrar primero la longitud de la subsecuencia común más larga de la array A[] y B[] y restarla del tamaño de la array B[] , lo que da el número de elementos a agregarse en la array A[] . Y agregue la cantidad C al costo de cada nuevo elemento agregado. Por lo tanto, el costo total viene dado por:
Costo = C*(N – LCS(A, B))
donde
LCS es la subsecuencia común más larga de los arreglos A[] y B[],
N es la longitud del arreglo A[] y
C es el costo de agregando cada elemento en la array B[].
Siga los pasos a continuación para resolver el problema:
- Cree una nueva array, digamos index[] e inicialícela con -1 y una array nums[] .
- Asigne cada elemento de la array B[] a su índice correspondiente en la array index[] .
- Recorra la array dada A[] e inserte los valores con sus valores asignados, es decir, el número de índice en la array nums[] y si el número de índice no es -1 .
- Ahora encuentre la subsecuencia creciente más larga de la array nums[] para obtener la longitud de la subsecuencia común más larga de las dos arrays dadas.
- Después de encontrar el LCS en los pasos anteriores, encuentre el valor del costo usando la fórmula discutida anteriormente.
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 length of the
// longest common subsequence
int findLCS(int* nums, int N)
{
int k = 0;
for (int i = 0; i < N; i++) {
// Find position where element
// is to be inserted
int pos = lower_bound(nums, nums + k,
nums[i])
- nums;
nums[pos] = nums[i];
if (k == pos) {
k = pos + 1;
}
}
// Return the length of LCS
return k;
}
// Function to find the minimum cost
// required to convert the sequence A
// exactly same as B
int minimumCost(int* A, int* B, int M,
int N, int C)
{
// Auxiliary array
int nums[1000000];
// Stores positions of elements of A[]
int index[1000000];
// Initialize index array with -1
memset(index, -1, sizeof(index));
for (int i = 0; i < N; i++) {
// Update the index array with
// index of corresponding
// elements of B
index[B[i]] = i;
}
int k = 0;
for (int i = 0; i < M; i++) {
// Place only A's array values
// with its mapped values
// into nums array
if (index[A[i]] != -1) {
nums[k++] = index[A[i]];
}
}
// Find LCS
int lcs_length = findLCS(nums, k);
// No of elements to be added
// in array A[]
int elements_to_be_added
= N - lcs_length;
// Stores minimum cost
int min_cost
= elements_to_be_added * C;
// Print the minimum cost
cout << min_cost;
}
// Driver Code
int main()
{
// Given array A[]
int A[] = { 1, 6, 3, 5, 10 };
int B[] = { 3, 1, 5 };
// Given C
int C = 2;
// Size of arr A
int M = sizeof(A) / sizeof(A[0]);
// Size of arr B
int N = sizeof(B) / sizeof(B[0]);
// Function Call
minimumCost(A, B, M, N, C);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
class GFG{
// Function to find lower_bound
static int LowerBound(int a[], int k,
int x)
{
int l = -1;
int r = k;
while (l + 1 < r)
{
int m = (l + r) >>> 1;
if (a[m] >= x)
{
r = m;
}
else
{
l = m;
}
}
return r;
}
// Function to find length of the
// longest common subsequence
static int findLCS(int[] nums, int N)
{
int k = 0;
for(int i = 0; i < N; i++)
{
// Find position where element
// is to be inserted
int pos = LowerBound(nums, k,
nums[i]);
nums[pos] = nums[i];
if (k == pos)
{
k = pos + 1;
}
}
// Return the length of LCS
return k;
}
// Function to find the minimum cost
// required to convert the sequence A
// exactly same as B
static int minimumCost(int[] A, int[] B,
int M, int N, int C)
{
// Auxiliary array
int[] nums = new int[100000];
// Stores positions of elements of A[]
int[] index = new int[100000];
// Initialize index array with -1
for(int i = 0; i < 100000; i++)
index[i] = -1;
for(int i = 0; i < N; i++)
{
// Update the index array with
// index of corresponding
// elements of B
index[B[i]] = i;
}
int k = 0;
for(int i = 0; i < M; i++)
{
// Place only A's array values
// with its mapped values
// into nums array
if (index[A[i]] != -1)
{
nums[k++] = index[A[i]];
}
}
// Find LCS
int lcs_length = findLCS(nums, k);
// No of elements to be added
// in array A[]
int elements_to_be_added = N - lcs_length;
// Stores minimum cost
int min_cost = elements_to_be_added * C;
// Print the minimum cost
System.out.println( min_cost);
return 0;
}
// Driver code
public static void main(String[] args)
{
// Given array A[]
int[] A = { 1, 6, 3, 5, 10 };
int[] B = { 3, 1, 5 };
// Given C
int C = 2;
// Size of arr A
int M = A.length;
// Size of arr B
int N = B.length;
// Function call
minimumCost(A, B, M, N, C);
}
}
// This code is contributed by sallagondaavinashreddy7
Python3
# Python3 program for the above approach # Function to find lower_bound def LowerBound(a, k, x): l = -1 r = k while (l + 1 < r): m = (l + r) >> 1 if (a[m] >= x): r = m else: l = m return r # Function to find length of the # longest common subsequence def findLCS(nums, N): k = 0 for i in range(N): # Find position where element # is to be inserted pos = LowerBound(nums, k, nums[i]) nums[pos] = nums[i] if (k == pos): k = pos + 1 # Return the length of LCS return k # Function to find the minimum cost # required to convert the sequence A # exactly same as B def minimumCost(A, B, M, N, C): # Auxiliary array nums = [0] * 100000 # Stores positions of elements of A[] # Initialize index array with -1 index = [-1] * 100000 for i in range(N): # Update the index array with # index of corresponding # elements of B index[B[i]] = i k = 0 for i in range(M): # Place only A's array values # with its mapped values # into nums array if (index[A[i]] != -1): k += 1 nums[k] = index[A[i]] # Find LCS lcs_length = findLCS(nums, k) # No of elements to be added # in array A[] elements_to_be_added = N - lcs_length # Stores minimum cost min_cost = elements_to_be_added * C # Print the minimum cost print( min_cost) # Driver Code # Given array A[] A = [ 1, 6, 3, 5, 10 ] B = [ 3, 1, 5 ] # Given C C = 2 # Size of arr A M = len(A) # Size of arr B N = len(B) # Function call minimumCost(A, B, M, N, C) # This code is contributed by divyeshrabadiya07
C#
// C# program for the above approach
using System;
class GFG{
// Function to find lower_bound
static int LowerBound(int[] a, int k,
int x)
{
int l = -1;
int r = k;
while (l + 1 < r)
{
int m = (l + r) >> 1;
if (a[m] >= x)
{
r = m;
}
else
{
l = m;
}
}
return r;
}
// Function to find length of the
// longest common subsequence
static int findLCS(int[] nums, int N)
{
int k = 0;
for(int i = 0; i < N; i++)
{
// Find position where element
// is to be inserted
int pos = LowerBound(nums, k,
nums[i]);
nums[pos] = nums[i];
if (k == pos)
{
k = pos + 1;
}
}
// Return the length of LCS
return k;
}
// Function to find the minimum cost
// required to convert the sequence A
// exactly same as B
static int minimumCost(int[] A, int[] B,
int M, int N, int C)
{
// Auxiliary array
int[] nums = new int[100000];
// Stores positions of elements of A[]
int[] index = new int[100000];
// Initialize index array with -1
for(int i = 0; i < 100000; i++)
index[i] = -1;
for(int i = 0; i < N; i++)
{
// Update the index array with
// index of corresponding
// elements of B
index[B[i]] = i;
}
int k = 0;
for(int i = 0; i < M; i++)
{
// Place only A's array values
// with its mapped values
// into nums array
if (index[A[i]] != -1)
{
nums[k++] = index[A[i]];
}
}
// Find LCS
int lcs_length = findLCS(nums, k);
// No of elements to be added
// in array A[]
int elements_to_be_added = N - lcs_length;
// Stores minimum cost
int min_cost = elements_to_be_added * C;
// Print the minimum cost
Console.WriteLine(min_cost);
return 0;
}
// Driver code
public static void Main()
{
// Given array A[]
int[] A = { 1, 6, 3, 5, 10 };
int[] B = { 3, 1, 5 };
// Given C
int C = 2;
// Size of arr A
int M = A.Length;
// Size of arr B
int N = B.Length;
// Function call
minimumCost(A, B, M, N, C);
}
}
// This code is contributed by code_hunt
Javascript
<script>
// javascript program for the above approach
// Function to find lower_bound
function LowerBound(a , k , x) {
var l = -1;
var r = k;
while (l + 1 < r) {
var m = (l + r) >>> 1;
if (a[m] >= x) {
r = m;
} else {
l = m;
}
}
return r;
}
// Function to find length of the
// longest common subsequence
function findLCS(nums , N) {
var k = 0;
for (i = 0; i < N; i++) {
// Find position where element
// is to be inserted
var pos = LowerBound(nums, k, nums[i]);
nums[pos] = nums[i];
if (k == pos) {
k = pos + 1;
}
}
// Return the length of LCS
return k;
}
// Function to find the minimum cost
// required to convert the sequence A
// exactly same as B
function minimumCost(A, B , M , N , C) {
// Auxiliary array
var nums = Array(100000).fill(0);
// Stores positions of elements of A
var index = Array(100000).fill(0);
// Initialize index array with -1
for (i = 0; i < 100000; i++)
index[i] = -1;
for (i = 0; i < N; i++) {
// Update the index array with
// index of corresponding
// elements of B
index[B[i]] = i;
}
var k = 0;
for (i = 0; i < M; i++) {
// Place only A's array values
// with its mapped values
// into nums array
if (index[A[i]] != -1) {
nums[k++] = index[A[i]];
}
}
// Find LCS
var lcs_length = findLCS(nums, k);
// No of elements to be added
// in array A
var elements_to_be_added = N - lcs_length;
// Stores minimum cost
var min_cost = elements_to_be_added * C;
// Print the minimum cost
document.write(min_cost);
return 0;
}
// Driver code
// Given array A
var A = [ 1, 6, 3, 5, 10 ];
var B = [ 3, 1, 5 ];
// Given C
var C = 2;
// Size of arr A
var M = A.length;
// Size of arr B
var N = B.length;
// Function call
minimumCost(A, B, M, N, C);
// This code contributed by umadevi9616
</script>
2
Complejidad de tiempo: O(N * Log N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por bolliranadheer y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA