Dadas dos arrays arr[] y cost[] donde cost[i] es el costo asociado con arr[i] , la tarea es encontrar el costo mínimo de elegir tres elementos de la array tal que arr[i] < arr[j ] <arr[j] .
Ejemplos:
Entrada: arr[] = {2, 4, 5, 4, 10}, cost[] = {40, 30, 20, 10, 40}
Salida: 90
(2, 4, 5), (2, 4, 10) ) y (4, 5, 10) son
los únicos tripletes válidos con un costo de 90.Entrada: arr[] = {1, 2, 3, 4, 5, 6}, cost[] = {10, 13, 11, 14, 15, 12}
Salida: 33
Enfoque ingenuo: un enfoque básico es ejecutar dos bucles anidados y verificar cada triplete posible. La complejidad temporal de este enfoque será O(n 3 ) .
Enfoque eficiente: un enfoque eficiente es fijar el elemento del medio y buscar el elemento más pequeño con el costo mínimo a su izquierda y el elemento más grande con el costo mínimo a su derecha en la array dada. Si se encuentra un triplete válido, actualice el costo mínimo ahora. La complejidad temporal de este enfoque será O(n 2 ) .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to return the minimum required cost
int minCost(int arr[], int cost[], int n)
{
// To store the cost of choosing three elements
int costThree = INT_MAX;
// Fix the middle element
for (int j = 0; j < n; j++) {
// Initialize cost of the first
// and the third element
int costI = INT_MAX, costK = INT_MAX;
// Search for the first element
// in the left subarray
for (int i = 0; i < j; i++) {
// If smaller element is found
// then update the cost
if (arr[i] < arr[j])
costI = min(costI, cost[i]);
}
// Search for the third element
// in the right subarray
for (int k = j + 1; k < n; k++) {
// If greater element is found
// then update the cost
if (arr[k] > arr[j])
costK = min(costK, cost[k]);
}
// If a valid triplet was found then
// update the minimum cost so far
if (costI != INT_MAX && costK != INT_MAX) {
costThree = min(costThree, cost[j]
+ costI
+ costK);
}
}
// No such triplet found
if (costThree == INT_MAX)
return -1;
return costThree;
}
// Driver code
int main()
{
int arr[] = { 2, 4, 5, 4, 10 };
int cost[] = { 40, 30, 20, 10, 40 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << minCost(arr, cost, n);
return 0;
}
Java
// Java implementation of the approach
class GFG
{
// Function to return the minimum required cost
static int minCost(int arr[], int cost[], int n)
{
// To store the cost of choosing three elements
int costThree = Integer.MAX_VALUE;
// Fix the middle element
for (int j = 0; j < n; j++)
{
// Initialize cost of the first
// and the third element
int costI = Integer.MAX_VALUE;
int costK = Integer.MAX_VALUE;
// Search for the first element
// in the left subarray
for (int i = 0; i < j; i++)
{
// If smaller element is found
// then update the cost
if (arr[i] < arr[j])
costI = Math.min(costI, cost[i]);
}
// Search for the third element
// in the right subarray
for (int k = j + 1; k < n; k++)
{
// If greater element is found
// then update the cost
if (arr[k] > arr[j])
costK = Math.min(costK, cost[k]);
}
// If a valid triplet was found then
// update the minimum cost so far
if (costI != Integer.MAX_VALUE &&
costK != Integer.MAX_VALUE)
{
costThree = Math.min(costThree, cost[j] +
costI + costK);
}
}
// No such triplet found
if (costThree == Integer.MAX_VALUE)
return -1;
return costThree;
}
// Driver code
public static void main (String[] args)
{
int arr[] = { 2, 4, 5, 4, 10 };
int cost[] = { 40, 30, 20, 10, 40 };
int n = arr.length;
System.out.println(minCost(arr, cost, n));
}
}
// This code is contributed by AnkitRai01
Python3
# Python3 implementation of the approach # Function to return the minimum required cost def minCost(arr, cost, n): # To store the cost of choosing three elements costThree = 10**9 # Fix the middle element for j in range(n): # Initialize cost of the first # and the third element costI = 10**9 costK = 10**9 # Search for the first element # in the left subarray for i in range(j): # If smaller element is found # then update the cost if (arr[i] < arr[j]): costI = min(costI, cost[i]) # Search for the third element # in the right subarray for k in range(j + 1, n): # If greater element is found # then update the cost if (arr[k] > arr[j]): costK = min(costK, cost[k]) # If a valid triplet was found then # update the minimum cost so far if (costI != 10**9 and costK != 10**9): costThree = min(costThree, cost[j] + costI + costK) # No such triplet found if (costThree == 10**9): return -1 return costThree # Driver code arr = [2, 4, 5, 4, 10] cost = [40, 30, 20, 10, 40] n = len(arr) print(minCost(arr, cost, n)) # This code is contributed by Mohit Kumar
C#
// C# implementation of the approach
using System;
class GFG
{
// Function to return the
// minimum required cost
static int minCost(int []arr,
int []cost, int n)
{
// To store the cost of
// choosing three elements
int costThree = int.MaxValue;
// Fix the middle element
for (int j = 0; j < n; j++)
{
// Initialize cost of the first
// and the third element
int costI = int.MaxValue;
int costK = int.MaxValue;
// Search for the first element
// in the left subarray
for (int i = 0; i < j; i++)
{
// If smaller element is found
// then update the cost
if (arr[i] < arr[j])
costI = Math.Min(costI, cost[i]);
}
// Search for the third element
// in the right subarray
for (int k = j + 1; k < n; k++)
{
// If greater element is found
// then update the cost
if (arr[k] > arr[j])
costK = Math.Min(costK, cost[k]);
}
// If a valid triplet was found then
// update the minimum cost so far
if (costI != int.MaxValue &&
costK != int.MaxValue)
{
costThree = Math.Min(costThree, cost[j] +
costI + costK);
}
}
// No such triplet found
if (costThree == int.MaxValue)
return -1;
return costThree;
}
// Driver code
static public void Main ()
{
int []arr = { 2, 4, 5, 4, 10 };
int []cost = { 40, 30, 20, 10, 40 };
int n = arr.Length;
Console.Write(minCost(arr, cost, n));
}
}
// This code is contributed by Sachin..
Javascript
<script>
// JavaScript implementation of the approach
// Function to return the minimum required cost
function minCost(arr,cost,n)
{
// To store the cost of choosing three elements
let costThree = Number.MAX_VALUE;
// Fix the middle element
for (let j = 0; j < n; j++)
{
// Initialize cost of the first
// and the third element
let costI = Number.MAX_VALUE;
let costK = Number.MAX_VALUE;
// Search for the first element
// in the left subarray
for (let i = 0; i < j; i++)
{
// If smaller element is found
// then update the cost
if (arr[i] < arr[j])
costI = Math.min(costI, cost[i]);
}
// Search for the third element
// in the right subarray
for (let k = j + 1; k < n; k++)
{
// If greater element is found
// then update the cost
if (arr[k] > arr[j])
costK = Math.min(costK, cost[k]);
}
// If a valid triplet was found then
// update the minimum cost so far
if (costI != Number.MAX_VALUE &&
costK != Number.MAX_VALUE)
{
costThree = Math.min(costThree, cost[j] +
costI + costK);
}
}
// No such triplet found
if (costThree == Number.MAX_VALUE)
return -1;
return costThree;
}
// Driver code
let arr=[2, 4, 5, 4, 10];
let cost=[40, 30, 20, 10, 40 ];
let n = arr.length;
document.write(minCost(arr, cost, n));
// This code is contributed by unknown2108
</script>
Producción:
90
Publicación traducida automáticamente
Artículo escrito por manoje1729 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA