Maximize sum of ratios of N given fractions by incrementing numerator and denominators K times by 1 | Function to increment the K fractions from the given array to maximize the sum of ratios of the given fractions ; Size of the array ; Max priority queue ; Iterate through the array ; Insert the incremented value if an operation is performed on the ith index ; Loop to perform K operations ; Increment the numerator and denominator of ith fraction ; Add the incremented value ; Stores the average ratio ; Return the ratio ; Driver Code
function maxAverageRatio ( arr , K ) { var N = arr . length ; var q = [ ] ; for ( var i = 0 ; i < N ; i ++ ) { var extra = ( ( arr [ i ] [ 0 ] + 1 ) / ( arr [ i ] [ 1 ] + 1 ) ) - ( arr [ i ] [ 0 ] / arr [ i ] [ 1 ] ) ; q . push ( [ extra , i ] ) ; } q . sort ( ) ; while ( K -- ) { var i = q [ q . length - 1 ] [ 1 ] ; q . pop ( ) ; arr [ i ] [ 0 ] += 1 ; arr [ i ] [ 1 ] += 1 ; var extra = ( ( arr [ i ] [ 0 ] + 1 ) / ( arr [ i ] [ 1 ] + 1 ) ) - ( arr [ i ] [ 0 ] / arr [ i ] [ 1 ] ) ; q . push ( [ extra , i ] ) ; q . sort ( ) ; } var ans = 0 ; for ( var i = 0 ; i < N ; i ++ ) { ans += ( arr [ i ] [ 0 ] / arr [ i ] [ 1 ] ) ; } return ans / N ; } var arr = [ [ 1 , 2 ] , [ 3 , 5 ] , [ 2 , 2 ] ] ; var K = 2 ; document . write ( maxAverageRatio ( arr , K ) . toFixed ( 6 ) ) ;