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