Maximize sum of ratios of N given fractions by incrementing numerator and denominators K times by 1 | C ++ program for the above approach ; 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; double maxAverageRatio ( vector < vector < int > > & arr , int K ) { int N = arr . size ( ) ; priority_queue < pair < double , int > > q ; for ( int i = 0 ; i < N ; i ++ ) { double extra = ( ( ( double ) arr [ i ] [ 0 ] + 1 ) / ( ( double ) arr [ i ] [ 1 ] + 1 ) ) - ( ( double ) arr [ i ] [ 0 ] / ( double ) arr [ i ] [ 1 ] ) ; q . push ( make_pair ( extra , i ) ) ; } while ( K -- ) { int i = q . top ( ) . second ; q . pop ( ) ; arr [ i ] [ 0 ] += 1 ; arr [ i ] [ 1 ] += 1 ; double extra = ( ( ( double ) arr [ i ] [ 0 ] + 1 ) / ( ( double ) arr [ i ] [ 1 ] + 1 ) ) - ( ( double ) arr [ i ] [ 0 ] / ( double ) arr [ i ] [ 1 ] ) ; q . push ( make_pair ( extra , i ) ) ; } double ans = 0 ; for ( int i = 0 ; i < N ; i ++ ) { ans += ( ( double ) arr [ i ] [ 0 ] / ( double ) arr [ i ] [ 1 ] ) ; } return ans / N ; } int main ( ) { vector < vector < int > > arr = { { 1 , 2 } , { 3 , 5 } , { 2 , 2 } } ; int K = 2 ; cout << maxAverageRatio ( arr , K ) ; return 0 ; }