Dada una array arr[] que consiste en N pares y un entero positivo M , la tarea es maximizar el promedio de la relación de los pares incrementando el primer y segundo elemento de cualquier par en 1 exactamente M veces.
Ejemplos:
Entrada: arr[] = {{1, 2}, {3, 5}, {2, 2}}, M = 2
Salida: 0.783333
Explicación:
A continuación se muestran las operaciones realizadas:
Operación 1: Incrementa el primer y segundo elemento de empareja {1, 2} por 1. Ahora, la array se modifica a {{2, 3}, {3, 5}, {2, 2}}.
Operación 2: Incremente el primer y segundo elemento del par {2, 3} en 1. Ahora, la array se modifica a {{3, 4}, {3, 5}, {2, 2}}.
Luego de las operaciones anteriores, el promedio de la razón de los pares es ((3/4) + (3/5) + (2/2))/3 = 0.7833 que es el máximo posible.Entrada: arr[] = {{2, 5}, {3, 5}}, M = 3
Salida: 0,619048
Enfoque: el problema dado se puede resolver almacenando el aumento incurrido en la relación aplicando la operación en los pares usando Max-heap y luego sigue extrayendo los valores M veces del montón y agrégalos a la suma total. Siga los pasos a continuación para resolver el problema:
- Inicialice una cola de prioridad , digamos PQ de pares para almacenar el cambio correspondiente en el promedio y el índice del par si se le aplica una operación.
- Inicialice una variable, diga suma como 0 para almacenar el promedio máximo de la relación de los pares.
- Recorra la array dada de pares arr[] y encuentre el aumento en la proporción después de agregar 1 a ambos valores del par y empuje el valor a la cola de prioridad PQ . Además, sume la razón del i -ésimo par a la suma variable .
- Iterar hasta que el valor de M sea positivo y realizar los siguientes pasos:
- Extraiga el elemento superior de la cola de prioridad PQ y agregue el aumento en la proporción a la suma .
- Actualice el valor de ese par y empuje el nuevo aumento en la relación del par en la cola de prioridad PQ .
- Después de completar los pasos anteriores, imprima el valor de la suma dividida por N como resultado.
A continuación se muestra la implementación del enfoque anterior:
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 operation
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
double 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 Code
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;
}
Python3
# python program for the above approach # Function to find the change in the # ratio in pair after applying operation def 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 increments def 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 Code if __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.
Javascript
<script>
// JavaScript program for the above approach
// Function to find the change in the
// ratio in pair after applying operation
function 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 increments
function 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 Code
let 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>
Producción:
0.783333
Complejidad de tiempo: O(M*log N)
Espacio auxiliar: O(N)