Given an array arr[] consisting of N pairs and a positive integer M, the task is to maximize the average of the ratio of the pairs by incrementing the first and second elements of any pair by 1 exactly M times.
Examples:
Input: arr[] = {{1, 2}, {3, 5}, {2, 2}}, M = 2
Output: 0.783333
Explanation:
Below are the operations performed:
Operation 1: Increment the first and second element of pair {1, 2} by 1. Now, the array modifies to {{2, 3}, {3, 5}, {2, 2}}.
Operation 2: Increment the first and second element of pair {2, 3} by 1. Now, the array modifies to {{3, 4}, {3, 5}, {2, 2}}.
After the above operations, the average of the ratio of the pairs is ((3/4) + (3/5) + (2/2))/3 = 0.7833 which is the maximum possible.Input: arr[] = {{2, 5}, {3, 5}}, M = 3
Output: 0.619048
Approach: The given problem can be solved by storing the increase incurred in the ratio by applying operation on the pairs using Max-heap and then keep popping the values M times from the heap and add to the overall sum. Follow the steps below to solve the problem:
- Initialize a priority queue, say PQ of pairs to store the corresponding change in average and the index of the pair if one operation is applied on it.
- Initialize a variable, say sum as 0 to store the maximum average of the ratio of the pairs.
- Traverse the given array of pairs arr[] and find the increase in the ratio after adding 1 to both the values of the pair and push the value to priority queue PQ. Also, add the ratio of the ith pair to the variable sum.
- Iterate until the value of M is positive and perform the following steps:
- Pop the top element of the priority queue PQ and add the increase in the ratio to the sum.
- Update the value of that pair and push the new increase in the ratio of the pair in the priority queue PQ.
- After completing the above steps, print the value of the sum divided by N as the result.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the change in the// ratio in pair after applying operationdouble change(int pass, int total){ double currentPassRatio, newPassRatio; double increase; // Stores the current ratio currentPassRatio = ((double)pass) / total; // Stores the new ratio newPassRatio = ((double)(pass + 1)) / (total + 1); // Stores the increase in ratio increase = newPassRatio - currentPassRatio; // Returns the change return increase;}// Function to find the maximum// average of the ratio of the// pairs by applying M incrementsdouble maximumAverage( vector<vector<int> > v, int M, int N){ // Stores the required result double sum = 0; double increase, average; // Declare a priority queue // for storing the increments priority_queue<pair<double, int> > pq; for (int i = 0; i < N; i++) { // Store the increase in the ratio // after applying one operation increase = change(v[i][0], v[i][1]); // Push the increased value and // index value in priority queue pq.push({ increase, i }); // Store the ratio average = v[i][0] * 1.0 / v[i][1]; // Update the value of sum sum += average; } // Iterate while M > 0 while (M > 0) { // Add the maximum change // to the sum sum += pq.top().first; int i = pq.top().second; // Remove the element from // the priority queue pq.pop(); // Increase the pairs elements // by 1 on which operation // is applied v[i][0] += 1; v[i][1] += 1; // Push the updated change of // the pair in priority queue pq.push({ change(v[i][0], v[i][1]), i }); // Decrease the operation count M--; } // Update the value of the sum by // dividing it by N double ans = sum / N; // Return the result return ans;}// Driver Codeint 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;} |
Java
import java.util.*;// Comparer for the SortedListclass DescendingComparer<T extends Comparable<T> > implements Comparator<T> { public int compare(T x, T y) { if (x == null) { return -1; } if (y == null) { return 1; } return x.compareTo(y); }}class GFG { // Function to find the change in the // ratio in pair after applying operation static double change(int pass, int total) { double currentPassRatio, newPassRatio; double increase; // Stores the current ratio currentPassRatio = ((double)pass) / total; // Stores the new ratio newPassRatio = ((double)(pass + 1)) / (total + 1); // Stores the increase in ratio increase = newPassRatio - currentPassRatio; // Returns the change return increase; } // Function to find the maximum // average of the ratio of the // pairs by applying M increments static double maximumAverage(List<List<Integer> > v, int M, int N) { // Stores the required result double sum = 0; double increase, average; // Declare a priority queue // for storing the increments PriorityQueue<Double> pq = new PriorityQueue<>( new DescendingComparer<Double>()); for (int i = 0; i < N; i++) { // Store the increase in the ratio // after applying one operation increase = change(v.get(i).get(0), v.get(i).get(1)); // Push the increased value and // index value in priority queue pq.add(increase); // Store the ratio average = v.get(i).get(0) * 1.0 / (1.0 * v.get(i).get(1)); // Update the value of sum sum += average; } // Iterate while M > 0 while (M > 0) { // Add the maximum change // to the sum // Remove the element from // the priority queue sum += pq.poll(); // Decrease the operation count M--; } // Update the value of the sum by // dividing it by N double ans = sum / (1.0 * N); // Return the result return ans; } // Main function public static void main(String[] args) { List<List<Integer> > V = new ArrayList<>(); V.add(Arrays.asList(1, 2)); V.add(Arrays.asList(3, 5)); V.add(Arrays.asList(2, 2)); int M = 2; int N = V.size(); System.out.println(maximumAverage(V, M, N)); }}// This code is contributed by phasing17. |
Python3
# python program for the above approach# Function to find the change in the# ratio in pair after applying operationdef change(pas, total): # Stores the current ratio currentPassRatio = pas/ total # Stores the new ratio newPassRatio = (pas + 1) / (total + 1) # Stores the increase in ratio increase = newPassRatio - currentPassRatio # Returns the change return increase# Function to find the maximum# average of the ratio of the# pairs by applying M incrementsdef maximumAverage(v, M, N): # Stores the required result sum = 0 increase, average = 0, 0 # Declare a priority queue # for storing the increments pq = [] for i in range(N): # Store the increase in the ratio # after applying one operation increase = change(v[i][0], v[i][1]) # Push the increased value and # index value in priority queue pq.append([increase, i ]) # Store the ratio average = v[i][0] * 1.0 / v[i][1] # Update the value of sum sum += average pq = sorted(pq) # Iterate while M > 0 while (M > 0): # Add the maximum change # to the sum sum += pq[-1][0] i = pq[-1][1] # Remove the element from # the priority queue del pq[-1] # Increase the pairs elements # by 1 on which operation # is applied v[i][0] += 1 v[i][1] += 1 # Push the updated change of # the pair in priority queue pq.append([change(v[i][0], v[i][1]), i]) # Decrease the operation count M -= 1 pq = sorted(pq) # Update the value of the sum by # dividing it by N ans = sum / N # Return the result return ans# Driver Codeif __name__ == '__main__': V = [[1, 2], [3, 5], [2, 2]] M = 2 N = len(V) print (round(maximumAverage(V, M, N),6)) # This code is contributed by mohit kumar 29. |
C#
// C# Program to find maximum average of the ratio of the pairs// by applying M incrementsusing System;using System.Collections.Generic;using System.Linq;// Comparer for the SortedListclass DescendingComparer<T> : IComparer<T> { public int Compare(T x, T y) { if (x == null) return -1; if (y == null) return 1; return Comparer<T>.Default.Compare(y, x); }}class Program { // Function to find the change in the // ratio in pair after applying operation static double Change(int pass, int total) { double currentPassRatio, newPassRatio; double increase; // Stores the current ratio currentPassRatio = ((double)pass) / total; // Stores the new ratio newPassRatio = ((double)(pass + 1)) / (total + 1); // Stores the increase in ratio increase = newPassRatio - currentPassRatio; // Returns the change return increase; } // Function to find the maximum // average of the ratio of the // pairs by applying M increments static double MaximumAverage(List<List<int> > v, int M, int N) { // Stores the required result double sum = 0; double increase, average; // Declare a priority queue // for storing the increments var pq = new SortedList<double, int>( new DescendingComparer<double>()); for (int i = 0; i < N; i++) { // Store the increase in the ratio // after applying one operation increase = Change(v[i][0], v[i][1]); // Push the increased value and // index value in priority queue pq.Add(increase, i); // Store the ratio average = v[i][0] * 1.0 / v[i][1]; // Update the value of sum sum += average; } // Iterate while M > 0 while (M > 0) { // Add the maximum change // to the sum sum += pq.First().Key; int i = pq.First().Value; // Remove the element from // the priority queue pq.RemoveAt(0); // Increase the pairs elements // by 1 on which operation // is applied v[i][0] += 1; v[i][1] += 1; // Push the updated change of // the pair in priority queue pq.Add(Change(v[i][0], v[i][1]), i); // Decrease the operation count M--; } // Update the value of the sum by // dividing it by N double ans = sum / N; // Return the result return ans; } // Main function static void Main(string[] args) { var V = new List<List<int> >{ new List<int>{ 1, 2 }, new List<int>{ 3, 5 }, new List<int>{ 2, 2 } }; int M = 2; int N = V.Count; Console.WriteLine(MaximumAverage(V, M, N)); }}// This code is contributed by phasing17. |
Javascript
<script>// JavaScript program for the above approach// Function to find the change in the// ratio in pair after applying operationfunction change(pass,total){ let currentPassRatio, newPassRatio; let increase; // Stores the current ratio currentPassRatio = (pass) / total; // Stores the new ratio newPassRatio = ((pass + 1)) / (total + 1); // Stores the increase in ratio increase = newPassRatio - currentPassRatio; // Returns the change return increase;}// Function to find the maximum// average of the ratio of the// pairs by applying M incrementsfunction maximumAverage(v,M,N){ // Stores the required result let sum = 0; let increase, average; // Declare a priority queue // for storing the increments let pq=[]; for (let i = 0; i < N; i++) { // Store the increase in the ratio // after applying one operation increase = change(v[i][0], v[i][1]); // Push the increased value and // index value in priority queue pq.push([ increase, i ]); // Store the ratio average = v[i][0] * 1.0 / v[i][1]; // Update the value of sum sum += average; } pq.sort(function(a,b){return a[0]-b[0]}); // Iterate while M > 0 while (M > 0) { // Add the maximum change // to the sum sum += pq[pq.length-1][0]; let i = pq[pq.length-1][1]; // Remove the element from // the priority queue pq.pop(); // Increase the pairs elements // by 1 on which operation // is applied v[i][0] += 1; v[i][1] += 1; // Push the updated change of // the pair in priority queue pq.push([ change(v[i][0], v[i][1]), i ]); // Decrease the operation count M--; pq.sort(function(a,b){return a[0]-b[0]}); } // Update the value of the sum by // dividing it by N let ans = sum / N; // Return the result return ans;}// Driver Codelet V=[[ 1, 2 ], [ 3, 5 ], [ 2, 2 ] ];let M = 2;let N=V.length;document.write( maximumAverage(V, M, N).toFixed(6));// This code is contributed by patel2127</script> |
Output:
0.783333
Time Complexity: O(M*log N)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
