Dados dos enteros positivos X e Y y un arreglo arr[] que consta de N enteros positivos tales que arr[i] representa la altura de la i -ésima persona y hay un túnel de altura H , la tarea es encontrar el costo mínimo total se requiere que pasen todas las N personas a través del túnel dado, como máximo dos personas cuya suma de alturas sea menor que H pueden pasar a la vez de acuerdo con las siguientes reglas:
- Cuando dos personas pasan por el túnel a la vez, entonces el costo es Y.
- Cuando una persona pasa por el túnel a la vez, el costo es X.
Nota: Todos los elementos de la array son menores que H .
Ejemplos:
Entrada: arr[] = {1, 3, 4, 4, 2}, X = 4, Y = 6, H = 9
Salida: 16
Explicación:
Considere el paso de personas según el siguiente orden:
- Persona 1 y Persona 4 que tienen alturas 1 y 4 respectivamente tienen la suma de alturas como 1 + 4 = 5 < H(= 9). Por lo tanto, el costo de esta operación es Y(= 6).
- Persona 2 y Persona 3 que tienen alturas 3 y 4 respectivamente tienen la suma de alturas como 3 + 4 = 7 < H(= 9). Por lo tanto, el costo de esta operación es Y(= 6).
- La persona 5 tiene una altura de 3 que es menor que H(= 9). Por lo tanto, el costo de esta operación es X( = 4).
Por tanto, el coste total es 6 + 6 + 4 = 16, que es el mínimo entre todas las combinaciones posibles.
Entrada: arr[] = {1, 3, 4}, X = 4, Y = 6, H = 9
Salida: 10
Enfoque: el problema dado se puede resolver utilizando el enfoque codicioso y la técnica de dos punteros . La idea es elegir aquellas dos personas cuya suma de las alturas sea menor que H con el costo de Y . De lo contrario, elija la persona de altura máxima entre las dos personas y páselas al túnel con el costo de X . Siga los pasos a continuación para resolver el problema:
- Ordene la array dada arr[] en orden creciente .
- Inicialice dos punteros, digamos i y j como 0 y (N – 1) respectivamente para que apunten a los extremos de la array.
- Iterar hasta que el valor de i sea menor que j y realizar los siguientes pasos:
- Si la suma de los valores de arr[i] y arr[j] es menor que H , entonces incrementa el valor del costo en Y e incrementa el valor de i y disminuye el valor de j en 1 .
- De lo contrario, disminuya el valor de j en 1 y actualice el valor de cost en X .
- Si el valor de i y j son iguales, incremente el valor del costo en X.
- Después de completar los pasos anteriores, imprima el valor del costo como el costo mínimo resultante.
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 total
// cost of passing at most two-person
// at a time through the tunnel
int minimumCost(int arr[], int N, int H,
int X, int Y)
{
// Stores the resultant cost
int cost = 0;
// Sort the given array
sort(arr, arr + N);
// Initialize two pointers
int i = 0, j = N - 1;
// Iterate until i is less than j
while (i < j) {
// If the sum of values at
// i and j is less than H
if (arr[i] + arr[j] < H) {
// Increment the cost
cost += Y;
// Update the pointers
i++;
j--;
}
// Otherwise
else {
cost += X;
j--;
}
}
// If i and j points to the same
// element, then that person is
// not passed to the tunnel
if (i == j)
cost += X;
// Return the minimum of the total
// cost and cost of passing all the
// person individually
return min(cost, N * X);
}
// Driver Code
int main()
{
int arr[] = { 1, 3, 4, 4, 2 };
int X = 4, Y = 6, H = 9;
int N = sizeof(arr) / sizeof(arr[0]);
cout << minimumCost(arr, N, H, X, Y);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
import java.util.Arrays;
class GFG{
// Function to find the minimum total
// cost of passing at most two-person
// at a time through the tunnel
public static int minimumCost(int arr[], int N, int H,
int X, int Y)
{
// Stores the resultant cost
int cost = 0;
// Sort the given array
Arrays.sort(arr);
// Initialize two pointers
int i = 0, j = N - 1;
// Iterate until i is less than j
while (i < j)
{
// If the sum of values at
// i and j is less than H
if (arr[i] + arr[j] < H)
{
// Increment the cost
cost += Y;
// Update the pointers
i++;
j--;
}
// Otherwise
else
{
cost += X;
j--;
}
}
// If i and j points to the same
// element, then that person is
// not passed to the tunnel
if (i == j)
cost += X;
// Return the minimum of the total
// cost and cost of passing all the
// person individually
return Math.min(cost, N * X);
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 1, 3, 4, 4, 2 };
int X = 4, Y = 6, H = 9;
int N = arr.length;
System.out.println(minimumCost(arr, N, H, X, Y));
}
}
// This code is contributed by Potta Lokesh
Python3
# Python 3 program for the above approach # Function to find the minimum total # cost of passing at most two-person # at a time through the tunnel def minimumCost(arr, N, H, X, Y): # Stores the resultant cost cost = 0 # Sort the given array arr.sort() # Initialize two pointers i = 0 j = N - 1 # Iterate until i is less than j while (i < j): # If the sum of values at # i and j is less than H if (arr[i] + arr[j] < H): # Increment the cost cost += Y # Update the pointers i += 1 j -= 1 # Otherwise else: cost += X j -= 1 # If i and j points to the same # element, then that person is # not passed to the tunnel if (i == j): cost += X # Return the minimum of the total # cost and cost of passing all the # person individually return min(cost, N * X) # Driver Code if __name__ == '__main__': arr = [1, 3, 4, 4, 2] X = 4 Y = 6 H = 9 N = len(arr) print(minimumCost(arr, N, H, X, Y)) # This code is contributed by bgangwar59.
C#
// C# program for the above approach
using System;
class GFG {
// Function to find the minimum total
// cost of passing at most two-person
// at a time through the tunnel
static int minimumCost(int[] arr, int N, int H, int X,
int Y)
{
// Stores the resultant cost
int cost = 0;
// Sort the given array
Array.Sort(arr);
// Initialize two pointers
int i = 0, j = N - 1;
// Iterate until i is less than j
while (i < j) {
// If the sum of values at
// i and j is less than H
if (arr[i] + arr[j] < H) {
// Increment the cost
cost += Y;
// Update the pointers
i++;
j--;
}
// Otherwise
else {
cost += X;
j--;
}
}
// If i and j points to the same
// element, then that person is
// not passed to the tunnel
if (i == j)
cost += X;
// Return the minimum of the total
// cost and cost of passing all the
// person individually
return Math.Min(cost, N * X);
}
// Driver code
public static void Main()
{
int[] arr = { 1, 3, 4, 4, 2 };
int X = 4, Y = 6, H = 9;
int N = arr.Length;
Console.WriteLine(minimumCost(arr, N, H, X, Y));
}
}
// This code is contributed by subhammahato348.
Javascript
<script>
// JavaScript program for the above approach
// Function to find the minimum total
// cost of passing at most two-person
// at a time through the tunnel
function minimumCost(arr, N, H, X, Y)
{
// Stores the resultant cost
let cost = 0;
// Sort the given array
arr.sort(function(a, b){return a - b});
// Initialize two pointers
let i = 0, j = N - 1;
// Iterate until i is less than j
while (i < j)
{
// If the sum of values at
// i and j is less than H
if (arr[i] + arr[j] < H)
{
// Increment the cost
cost += Y;
// Update the pointers
i++;
j--;
}
// Otherwise
else
{
cost += X;
j--;
}
}
// If i and j points to the same
// element, then that person is
// not passed to the tunnel
if (i == j)
cost += X;
// Return the minimum of the total
// cost and cost of passing all the
// person individually
return Math.min(cost, N * X);
}
// Driver Code
let arr = [ 1, 3, 4, 4, 2 ];
let X = 4, Y = 6, H = 9;
let N = arr.length;
document.write(minimumCost(arr, N, H, X, Y));
// This code is contributed by Potta Lokesh
</script>
Producción
16
Complejidad de tiempo: O(N*log N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por kartikey134 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA