Maximize average of the ratios of N pairs by M increments | C ++ program for the above approach ; 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; double change ( int pass , int total ) { double currentPassRatio , newPassRatio ; double increase ; currentPassRatio = ( ( double ) pass ) / total ; newPassRatio = ( ( double ) ( pass + 1 ) ) / ( total + 1 ) ; increase = newPassRatio - currentPassRatio ; return increase ; } double maximumAverage ( vector < vector < int > > v , int M , int N ) { double sum = 0 ; double increase , average ; priority_queue < pair < double , int > > pq ; for ( int 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 ; } while ( M > 0 ) { sum += pq . top ( ) . first ; int i = pq . top ( ) . second ; pq . pop ( ) ; v [ i ] [ 0 ] += 1 ; v [ i ] [ 1 ] += 1 ; pq . push ( { change ( v [ i ] [ 0 ] , v [ i ] [ 1 ] ) , i } ) ; M -- ; } double ans = sum / N ; return ans ; } int main ( ) { vector < vector < int > > V = { { 1 , 2 } , { 3 , 5 } , { 2 , 2 } } ; int M = 2 ; int N = V . size ( ) ; cout << maximumAverage ( V , M , N ) ; return 0 ; }