Dada una array A[] que consta de N enteros y dos enteros X e Y , la tarea es encontrar la suma máxima de los promedios de cada subsecuencia obtenida al dividir la array en subsecuencias de longitudes que se encuentran en el rango [X, Y] .
Nota: Los valores de X e Y son tales que siempre es posible hacer tales grupos.
Ejemplos:
Entrada: A[] = {4, 10, 6, 5}, X = 2, Y = 3
Salida: 12.50
Explicación:
Divide la array dada en dos grupos como {4, 10}, {6, 5} tal que sus tamaños se encuentra en el rango [2, 3].
La media del primer grupo = (4 + 10) / 2 = 7.
La media del segundo grupo = (6 + 5) / 2 = 5,5.
Por tanto, la suma de la media = 7 + 5,5 = 12,5, que es la mínima entre todos los grupos posibles.Entrada: A[] = {3, 3, 1}
Salida: 3,00
Enfoque: el problema dado se puede resolver utilizando el enfoque codicioso . La idea es ordenar la array en orden ascendente y elegir los grupos de tamaño X porque el promedio es inversamente proporcional al número de elementos. Finalmente, agregue los elementos restantes al último grupo. Siga los pasos a continuación para resolver el problema:
- Ordene la array dada arr[] en orden ascendente.
- Inicialice las variables, diga sum, res y count como 0 para almacenar la suma de los elementos de la array , el resultado y el recuento de elementos en el grupo actual.
- Iterar sobre el rango [0, N] usando la variable i y realizar los siguientes pasos:
- Agregue el valor de arr[i] a la variable sum y aumente el valor de count en 1 .
- Si el valor de count es igual a X , y los elementos restantes de la array no pueden formar un grupo, agréguelos al grupo actual y agregue el promedio en la variable res .
- En caso contrario, suma la media del grupo formado hasta el momento en la variable res .
- Después de completar los pasos anteriores, imprima el valor de res como respuesta.
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 maximum sum
// of average of groups
void maxAverage(int A[], int N, int X,
int Y)
{
// Sort the given array
sort(A, A + N);
int sum = 0;
// Stores the sum of averages
double res = 0;
// Stores count of array element
int count = 0;
for (int i = 0; i < N; i++) {
// Add the current value to
// the variable sum
sum += A[i];
// Increment the count by 1
count++;
// If the current size is X
if (count == X) {
// If the remaining elements
// can't become a group
if (N - i - 1 < X) {
i++;
int cnt = 0;
// Iterate until i is
// less than N
while (i < N) {
cnt++;
sum += A[i];
i++;
}
// Update the value of X
X = X + cnt;
// Update the average
res += (double)sum / double(X);
break;
}
// Find the average
res += (double)sum / double(X);
// Reset the sum and count
sum = 0;
count = 0;
}
}
// Print maximum sum of averages
cout << fixed << setprecision(2)
<< res << "\n";
}
// Driver Code
int main()
{
int A[] = { 4, 10, 6, 5 };
int N = sizeof(A) / sizeof(A[0]);
int X = 2, Y = 3;
maxAverage(A, N, X, Y);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to find the maximum sum
// of average of groups
static void maxAverage(int A[], int N, int X,
int Y)
{
// Sort the given array
Arrays.sort(A);
int sum = 0;
// Stores the sum of averages
double res = 0;
// Stores count of array element
int count = 0;
for(int i = 0; i < N; i++)
{
// Add the current value to
// the variable sum
sum += A[i];
// Increment the count by 1
count++;
// If the current size is X
if (count == X)
{
// If the remaining elements
// can't become a group
if (N - i - 1 < X)
{
i++;
int cnt = 0;
// Iterate until i is
// less than N
while (i < N)
{
cnt++;
sum += A[i];
i++;
}
// Update the value of X
X = X + cnt;
// Update the average
res += (double)sum / (double)(X);
break;
}
// Find the average
res += (double)sum / (double)(X);
// Reset the sum and count
sum = 0;
count = 0;
}
}
// Print maximum sum of averages
System.out.println(res);
}
// Driver Code
public static void main(String[] args)
{
int A[] = { 4, 10, 6, 5 };
int N = A.length;
int X = 2, Y = 3;
maxAverage(A, N, X, Y);
}
}
// This code is contributed by gauravrajput1
Python3
# Python 3 program for the above approach # Function to find the maximum sum # of average of groups def maxAverage(A,N,X,Y): # Sort the given array A.sort() sum = 0 # Stores the sum of averages res = 0 # Stores count of array element count = 0 for i in range(N): # Add the current value to # the variable sum sum += A[i] # Increment the count by 1 count += 1 # If the current size is X if (count == X): # If the remaining elements # can't become a group if (N - i - 1 < X): i += 1 cnt = 0 # Iterate until i is # less than N while (i < N): cnt += 1 sum += A[i] i += 1 # Update the value of X X = X + cnt # Update the average res += sum / X break # Find the average res += sum / X # Reset the sum and count sum = 0 count = 0 # Print maximum sum of averages print(res) # Driver Code if __name__ == '__main__': A = [4, 10, 6, 5] N = len(A) X = 2 Y = 3 maxAverage(A, N, X, Y) # This code is contributed by ipg2016107.
C#
// C# program for the above approach
using System;
public class GFG{
// Function to find the maximum sum
// of average of groups
static void maxAverage(int []A, int N, int X,
int Y)
{
// Sort the given array
Array.Sort(A);
int sum = 0;
// Stores the sum of averages
double res = 0;
// Stores count of array element
int count = 0;
for(int i = 0; i < N; i++)
{
// Add the current value to
// the variable sum
sum += A[i];
// Increment the count by 1
count++;
// If the current size is X
if (count == X)
{
// If the remaining elements
// can't become a group
if (N - i - 1 < X)
{
i++;
int cnt = 0;
// Iterate until i is
// less than N
while (i < N)
{
cnt++;
sum += A[i];
i++;
}
// Update the value of X
X = X + cnt;
// Update the average
res += (double)sum / (double)(X);
break;
}
// Find the average
res += (double)sum / (double)(X);
// Reset the sum and count
sum = 0;
count = 0;
}
}
// Print maximum sum of averages
Console.WriteLine(res);
}
// Driver Code
public static void Main(String[] args)
{
int []A = { 4, 10, 6, 5 };
int N = A.Length;
int X = 2, Y = 3;
maxAverage(A, N, X, Y);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// JavaScript program for the above approach
// Function to find the maximum sum
// of average of groups
function maxAverage(A, N, X, Y) {
// Sort the given array
A.sort(function (a, b) { return a - b; })
let sum = 0;
// Stores the sum of averages
let res = 0;
// Stores count of array element
let count = 0;
for (let i = 0; i < N; i++) {
// Add the current value to
// the variable sum
sum += A[i];
// Increment the count by 1
count++;
// If the current size is X
if (count == X) {
// If the remaining elements
// can't become a group
if (N - i - 1 < X) {
i++;
let cnt = 0;
// Iterate until i is
// less than N
while (i < N) {
cnt++;
sum += A[i];
i++;
}
// Update the value of X
X = X + cnt;
// Update the average
res += sum / X;
break;
}
// Find the average
res += sum / X;
// Reset the sum and count
sum = 0;
count = 0;
}
}
// Print maximum sum of averages
document.write(res.toPrecision(3))
}
// Driver Code
let A = [4, 10, 6, 5];
let N = A.length;
let X = 2, Y = 3;
maxAverage(A, N, X, Y);
// This code is contributed by Potta Lokesh
</script>
Producción:
12.50
Complejidad de tiempo: O(N * log N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por sujitmeshram y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA