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