Encuentre el costo mínimo para cruzar el río

Dado un número entero N , que es el número de aldeanos que necesitan cruzar un río, pero solo hay un bote en el que pueden viajar un máximo de 2 personas. Cada persona i tiene que pagar un precio específico P i para viajar solo en el barco. Si dos personas i, j viajan en el bote, entonces tienen que pagar max(P i , P j ) . La tarea es encontrar la cantidad mínima que todos los aldeanos deben pagar para cruzar el río.
Ejemplos: 
 

Entrada: Precio[] = {30, 40, 60, 70} 
Salida: 220 
P 1 y P 2 van juntos (lo que cuesta 40) 
y P 1 vuelve (coste total ahora 70). 
Ahora P 3 y P 4 van (costo total 140) y 
P 2 regresa (costo total 180) y 
finalmente P 1 y P 2 van juntos (costo total 220).
Entrada: Precio[] = {892, 124} 
Salida: 892 
 

Aproximación: Hay dos formas para que las dos personas más costosas crucen el río: 
 

  • Ambos cruzan el río con la persona más barata paso a paso. Así, el coste total será el coste de las dos personas caras + 2* (coste de la persona más barata) (por volver).
  • Las dos personas más baratas cruzan el río y la persona más barata vuelve. Ahora, la segunda persona más costosa cruza el río y la segunda persona más barata regresa. Entonces, el costo total será el costo de la persona más barata y más costosa más 2 * costo de la segunda persona más barata.
  • El costo total será el mínimo de las dos formas anteriores.

Consideremos el ejemplo que usamos arriba para entender el enfoque: 
P 1 = 30, P 2 = 40, P 3 = 60, P 4 = 70
Según el primer método, P 4 va con P 1 y P 1 regresa (el costo es P 4 + P 1 ). 
Ahora, P 3 va con P 1 y P 1 regresa (el costo de este viaje será P 4 + P 1 ). 
Entonces, el costo total de enviar a dos de las personas más costosas según el método 1 es P 4 +2*P 1 +P 3 = 190
Según el segundo método, P 2 va con P 1 y P 1 regresa (el costo es P 2 + P 1 ). 
Ahora, P 3 va con P 4 y P 2 regresa (el costo de este viaje será P 4 + P 2 ). 
Entonces, el costo total de enviar a las dos personas más costosas según el método 2 es P 4 +2*P 2 +P 1 = 180
Por lo tanto, el costo de enviar P 3 y P 4 será el mínimo de 2 métodos, es decir, 180.
Ahora, nos quedamos con P 1 y P 2a quienes tenemos que enviar juntos y el costo será 
P 2 = 40.
Entonces, el costo total del viaje es 180 + 40 = 220. 
 

A continuación se muestra la implementación del enfoque anterior: 
 

C++

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
#define ll long long int
 
// Function to return the minimum cost
int minimumCost(ll price[], int n)
{
 
    // Sort the price array
    sort(price, price + n);
    ll totalCost = 0;
 
    // Calculate minimum price
    // of n-2 most costly person
    for (int i = n - 1; i > 1; i -= 2) {
        if (i == 2) {
            totalCost += price[2] + price[0];
        }
        else {
 
            // Both the ways as discussed above
            ll price_first = price[i] + price[0] + 2 * price[1];
            ll price_second = price[i] + price[i - 1] + 2 * price[0];
            totalCost += min(price_first, price_second);
        }
    }
 
    // Calculate the minimum price
    // of the two cheapest person
    if (n == 1) {
        totalCost += price[0];
    }
    else {
        totalCost += price[1];
    }
 
    return totalCost;
}
 
// Driver code
int main()
{
    ll price[] = { 30, 40, 60, 70 };
    int n = sizeof(price) / sizeof(price[0]);
 
    cout << minimumCost(price, n);
 
    return 0;
}

Java

// Java implementation of the approach
import java.util.*;
 
class GFG
{
     
    // Function to return the minimum cost
    static long minimumCost(long price[], int n)
    {
     
        // Sort the price array
        Arrays.sort(price);
         
        long totalCost = 0;
     
        // Calculate minimum price
        // of n-2 most costly person
        for (int i = n - 1; i > 1; i -= 2)
        {
            if (i == 2)
            {
                totalCost += price[2] + price[0];
            }
            else
            {
     
                // Both the ways as discussed above
                long price_first = price[i] + price[0] + 2 * price[1];
                long price_second = price[i] + price[i - 1] + 2 * price[0];
                totalCost += Math.min(price_first, price_second);
            }
        }
     
        // Calculate the minimum price
        // of the two cheapest person
        if (n == 1)
        {
            totalCost += price[0];
        }
        else
        {
            totalCost += price[1];
        }
     
        return totalCost;
    }
     
    // Driver code
    public static void main (String[] args)
    {
        long price[] = { 30, 40, 60, 70 };
        int n = price.length;
     
        System.out.println(minimumCost(price, n));
    }
}
 
// This code is contributed by AnkitRai01

Python

# Python3 implementation of the approach
 
# Function to return the minimum cost
def minimumCost(price, n):
 
    # Sort the price array
    price = sorted(price)
    totalCost = 0
 
    # Calculate minimum price
    # of n-2 most costly person
    for i in range(n - 1, 1, -2):
        if (i == 2):
            totalCost += price[2] + price[0]
 
        else:
 
            # Both the ways as discussed above
            price_first = price[i] + price[0] + 2 * price[1]
            price_second = price[i] + price[i - 1] + 2 * price[0]
            totalCost += min(price_first, price_second)
 
    # Calculate the minimum price
    # of the two cheapest person
    if (n == 1):
        totalCost += price[0]
 
    else:
        totalCost += price[1]
 
    return totalCost
 
# Driver code
 
price = [30, 40, 60, 70]
n = len(price)
 
print(minimumCost(price, n))
 
# This code is contributed by mohit kumar 29

C#

// C# implementation of the approach
using System;
 
class GFG
{
     
    // Function to return the minimum cost
    static long minimumCost(long []price, int n)
    {
     
        // Sort the price array
        Array.Sort(price);
         
        long totalCost = 0;
     
        // Calculate minimum price
        // of n-2 most costly person
        for (int i = n - 1; i > 1; i -= 2)
        {
            if (i == 2)
            {
                totalCost += price[2] + price[0];
            }
            else
            {
     
                // Both the ways as discussed above
                long price_first = price[i] + price[0] + 2 * price[1];
                long price_second = price[i] + price[i - 1] + 2 * price[0];
                totalCost += Math.Min(price_first, price_second);
            }
        }
     
        // Calculate the minimum price
        // of the two cheapest person
        if (n == 1)
        {
            totalCost += price[0];
        }
        else
        {
            totalCost += price[1];
        }
     
        return totalCost;
    }
     
    // Driver code
    public static void Main ()
    {
        long []price = { 30, 40, 60, 70 };
        int n = price.Length;
     
        Console.WriteLine(minimumCost(price, n));
    }
}
 
// This code is contributed by AnkitRai01

Javascript

<script>
    // Javascript implementation of the approach
     
    // Function to return the minimum cost
    function minimumCost(price, n)
    {
       
        // Sort the price array
        price.sort();
           
        let totalCost = 0;
       
        // Calculate minimum price
        // of n-2 most costly person
        for (let i = n - 1; i > 1; i -= 2)
        {
            if (i == 2)
            {
                totalCost += price[2] + price[0];
            }
            else
            {
       
                // Both the ways as discussed above
                let price_first = price[i] + price[0] + 2 * price[1];
                let price_second = price[i] + price[i - 1] + 2 * price[0];
                totalCost += Math.min(price_first, price_second);
            }
        }
       
        // Calculate the minimum price
        // of the two cheapest person
        if (n == 1)
        {
            totalCost += price[0];
        }
        else
        {
            totalCost += price[1];
        }
       
        return totalCost;
    }
     
    let price = [ 30, 40, 60, 70 ];
    let n = price.length;
 
    document.write(minimumCost(price, n));
             
</script>
Producción: 

220

 

Complejidad de tiempo: O(n * log n)

Espacio Auxiliar: O(1)

Publicación traducida automáticamente

Artículo escrito por AshaRamMeena 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 *