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>
0.783333
Complejidad de tiempo: O(M*log N)
Espacio auxiliar: O(N)