Costo mínimo de pasar N personas a través de un túnel dado

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:

  1. 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).
  2. 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).
  3. 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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *