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>
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