Dado un entero positivo K y una array arr[] que consta de {numerador, denominador} de N fracciones, la tarea es encontrar la suma de la razón de las fracciones dadas después de incrementar los numeradores y los denominadores en 1 , K número de veces .
Ejemplos:
Entrada: arr[][] = {{1, 2}, {3, 5}, {2, 2}}, K = 2
Salida: 0,78333
Explicación:
la opción más óptima es incrementar la primera fracción K(= 2 ) numero de veces. Por lo tanto, la suma de la razón es (3/4 + 3/5 + 2/2) / 3 = 0,78333, que es el máximo posible.Entrada: arr[][] = {{1, 1}, {4, 5}}, K = 5
Salida : 0,95
Enfoque: El problema dado se puede resolver usando el Enfoque codicioso , la idea es incrementar esa fracción entre las fracciones dadas cuyo incremento maximiza la suma de las proporciones de las fracciones. Esta idea se puede implementar utilizando la cola de prioridad . Siga los pasos a continuación para resolver el problema:
- Inicialice un Max Heap , digamos PQ usando la cola de prioridad que almacena el valor que se incrementará en la relación promedio total si se realiza una operación en el i -ésimo índice para todos los valores de i en el rango [0, N) .
- Inserta todos los índices de la fracción en el arreglo arr[] en la cola de prioridad PQ con el valor incrementado de fracciones.
- Iterar sobre el rango [0, K – 1] y realizar los siguientes pasos:
- Haga estallar el elemento superior del PQ .
- Incrementa la fracción del índice reventado actual.
- Inserte todas las fracciones actuales en la array arr[] en la cola de prioridad PQ con el valor incrementado de fracciones.
- Después de completar los pasos anteriores, imprima la suma de las proporciones de todas las fracciones almacenadas en priority_queue PQ .
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 increment the K fractions
// from the given array to maximize the
// sum of ratios of the given fractions
double maxAverageRatio(
vector<vector<int> >& arr, int K)
{
// Size of the array
int N = arr.size();
// Max priority queue
priority_queue<pair<double, int> > q;
// Iterate through the array
for (int i = 0; i < N; i++) {
// Insert the incremented value
// if an operation is performed
// on the ith index
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));
}
// Loop to perform K operations
while (K--) {
int i = q.top().second;
q.pop();
// Increment the numerator and
// denominator of ith fraction
arr[i][0] += 1;
arr[i][1] += 1;
// Add the incremented value
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));
}
// Stores the average ratio
double ans = 0;
for (int i = 0; i < N; i++) {
ans += ((double)arr[i][0]
/ (double)arr[i][1]);
}
// Return the ratio
return ans / N;
}
// Driver Code
int main()
{
vector<vector<int> > arr
= { { 1, 2 }, { 3, 5 }, { 2, 2 } };
int K = 2;
cout << maxAverageRatio(arr, K);
return 0;
}
Python3
# Python 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 def maxAverageRatio(arr,k): #Size of the array N=len(arr) # Max priority queue q=[] # Iterate through the array for i in range(N): # Insert the incremented value # if an operation is performed # on the ith index extra = ((float(arr[i][0])+1)/(float(arr[i][1])+1))-(float(arr[i][0])/float(arr[i][1])) q.append([extra,i]) # Loop to perform K operations while(k>0): k=k-1 i=q[0][1] q.pop(0) # Increment the numerator and # denominator of ith fraction arr[i][0]=arr[i][0]+1 arr[i][1]=arr[i][1]+1 # Add the incremented value extra = ((float(arr[i][0])+1)/(float(arr[i][1])+1))-(float(arr[i][0])/float(arr[i][1])) q.append([extra,i]) # Stores the average ratio ans=0 for i in range(N): ans=ans+(float(arr[i][0])/float(arr[i][1])) # Return the ratio return ans/N # Driver Code arr = [ [ 1, 2 ], [ 3, 5 ], [ 2, 2 ] ] K = 2 print(maxAverageRatio(arr, K)) # This code is contributed by Pushpesh Raj
Javascript
<script>
// Javascript 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
function maxAverageRatio(arr, K)
{
// Size of the array
var N = arr.length;
// Max priority queue
var q = [];
// Iterate through the array
for (var i = 0; i < N; i++) {
// Insert the incremented value
// if an operation is performed
// on the ith index
var extra
= ((arr[i][0] + 1)
/ (arr[i][1] + 1))
- (arr[i][0]
/ arr[i][1]);
q.push([extra, i]);
}
q.sort();
// Loop to perform K operations
while (K--) {
var i = q[q.length-1][1];
q.pop();
// Increment the numerator and
// denominator of ith fraction
arr[i][0] += 1;
arr[i][1] += 1;
// Add the incremented value
var extra
= ((arr[i][0] + 1)
/ (arr[i][1] + 1))
- (arr[i][0]
/ arr[i][1]);
q.push([extra, i]);
q.sort();
}
// Stores the average ratio
var ans = 0;
for (var i = 0; i < N; i++) {
ans += (arr[i][0]
/ arr[i][1]);
}
// Return the ratio
return ans / N;
}
// Driver Code
var arr = [[1, 2 ], [3, 5], [2, 2 ]];
var K = 2;
document.write(maxAverageRatio(arr, K).toFixed(6));
// This code is contributed by rrrtnx.
</script>
0.783333
Complejidad de tiempo: O(K*log N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por kartikmodi y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA