Maximize average of the ratios of N pairs by M increments | Function to find the change in the ratio in pair after applying operation ; Stores the current ratio ; Stores the new ratio ; Stores the increase in ratio ; Returns the change ; Function to find the maximum average of the ratio of the pairs by applying M increments ; Stores the required result ; Declare a priority queue for storing the increments ; Store the increase in the ratio after applying one operation ; Push the increased value and index value in priority queue ; Store the ratio ; Update the value of sum ; Iterate while M > 0 ; Add the maximum change to the sum ; Remove the element from the priority queue ; Increase the pairs elements by 1 on which operation is applied ; Push the updated change of the pair in priority queue ; Decrease the operation count ; Update the value of the sum by dividing it by N ; Return the result ; Driver Code
function change ( pass , total ) { let currentPassRatio , newPassRatio ; let increase ; currentPassRatio = ( pass ) / total ; newPassRatio = ( ( pass + 1 ) ) / ( total + 1 ) ; increase = newPassRatio - currentPassRatio ; return increase ; } function maximumAverage ( v , M , N ) { let sum = 0 ; let increase , average ; let pq = [ ] ; for ( let i = 0 ; i < N ; i ++ ) { increase = change ( v [ i ] [ 0 ] , v [ i ] [ 1 ] ) ; pq . push ( [ increase , i ] ) ; average = v [ i ] [ 0 ] * 1.0 / v [ i ] [ 1 ] ; sum += average ; } pq . sort ( function ( a , b ) { return a [ 0 ] - b [ 0 ] } ) ; while ( M > 0 ) { sum += pq [ pq . length - 1 ] [ 0 ] ; let i = pq [ pq . length - 1 ] [ 1 ] ; pq . pop ( ) ; v [ i ] [ 0 ] += 1 ; v [ i ] [ 1 ] += 1 ; pq . push ( [ change ( v [ i ] [ 0 ] , v [ i ] [ 1 ] ) , i ] ) ; M -- ; pq . sort ( function ( a , b ) { return a [ 0 ] - b [ 0 ] } ) ; } let ans = sum / N ; return ans ; } let V = [ [ 1 , 2 ] , [ 3 , 5 ] , [ 2 , 2 ] ] ; let M = 2 ; let N = V . length ; document . write ( maximumAverage ( V , M , N ) . toFixed ( 6 ) ) ;