Minimize cost to reach end of an N | C ++ program for the above approach ; For priority_queue ; Function to calculate the minimum cost required to reach the end of Line ; Checks if possible to reach end or not ; Stores the stations and respective rate of fuel ; Stores the station index and cost of fuel and litres of petrol which is being fueled ; Iterate through the entire line ; Check if there is a station at current index ; Remove all the stations where fuel cannot be pumped ; If there is no station left to fill fuel in tank , it is not possible to reach end ; Stores the best station visited so far ; Pump fuel from the best station ; Update the count of litres taken from that station ; Update the bunk in queue ; Print the cost ; Driven Program ; Given value of N , K & M ; Given arrays ; Function call to calculate minimum cost to reach end of the line
#include <bits/stdc++.h> NEW_LINE using namespace std ; struct Compare { bool operator() ( array < int , 3 > a , array < int , 3 > b ) { return a [ 1 ] > b [ 1 ] ; } } ; void minCost ( int N , int K , int M , int a [ ] , int b [ ] ) { bool flag = true ; unordered_map < int , int > map ; for ( int i = 0 ; i < M ; i ++ ) { map [ a [ i ] ] = b [ i ] ; if ( i == M - 1 && K < N - a [ i ] ) { flag = false ; break ; } else if ( i < M - 1 && K < a [ i + 1 ] - a [ i ] ) { flag = false ; break ; } } if ( ! flag ) { cout << -1 ; return ; } priority_queue < array < int , 3 > , vector < array < int , 3 > > , Compare > pq ; int cost = 0 ; flag = false ; for ( int i = 0 ; i < N ; i ++ ) { if ( map . find ( i ) != map . end ( ) ) { array < int , 3 > arr = { i , map [ i ] , 0 } ; pq . push ( arr ) ; } while ( pq . size ( ) > 0 && pq . top ( ) [ 2 ] == K ) pq . pop ( ) ; if ( pq . size ( ) == 0 ) { flag = true ; break ; } array < int , 3 > best_bunk = pq . top ( ) ; pq . pop ( ) ; cost += best_bunk [ 1 ] ; best_bunk [ 2 ] ++ ; pq . push ( best_bunk ) ; } if ( flag ) { cout << -1 << " STRNEWLINE " ; return ; } cout << cost << " STRNEWLINE " ; } int main ( ) { int N = 10 , K = 3 , M = 4 ; int a [ ] = { 0 , 1 , 4 , 6 } ; int b [ ] = { 5 , 2 , 2 , 4 } ; minCost ( N , K , M , a , b ) ; return 0 ; }