Minimize cost to convert all characters of a binary string to 0 s | C ++ program to implement the above approach ; Function to get the minimum Cost to convert all characters of given string to 0 s ; Stores the range of indexes of characters that need to be flipped ; Stores the number of times current character is flipped ; Stores minimum cost to get the required string ; Traverse the given string ; Remove all value from pq whose value is less than i ; Update flip ; If current character is flipped odd times ; If current character contains non - zero value ; Update flip ; Update cost ; Append R [ i ] into pq ; Driver Code ; Function call
#include <bits/stdc++.h> NEW_LINE using namespace std ; int minCost ( string str , int N , int R [ ] , int C [ ] ) { priority_queue < int , vector < int > , greater < int > > pq ; int flip = 0 ; int cost = 0 ; for ( int i = 0 ; i < N ; i ++ ) { while ( pq . size ( ) > 0 and pq . top ( ) < i ) { pq . pop ( ) ; flip -- ; } if ( flip % 2 == 1 ) { str [ i ] = '1' - str [ i ] + '0' ; } if ( str [ i ] == '1' ) { flip ++ ; cost += C [ i ] ; pq . push ( R [ i ] ) ; } } return cost ; } int main ( ) { string str = "1010" ; int R [ ] = { 1 , 2 , 2 , 3 } ; int C [ ] = { 3 , 1 , 2 , 3 } ; int N = str . length ( ) ; cout << minCost ( str , N , R , C ) ; }