Maximizar la suma de las medias de dos subconjuntos formados al dividir el Array dado en ellos

Dada una array arr[] de tamaño N, la tarea es encontrar la suma máxima de las medias de 2 subconjuntos no vacíos de la array dada de modo que cada elemento sea parte de uno de los subconjuntos.

Ejemplos :

Entrada:   N = 2, arr[] = {1, 3}
Salida:  4.00
Explicación: Dado que solo hay dos elementos, haga dos subconjuntos como {1} y {3}.
Sus tamaños son 1, por lo que la media para ambos será 1,00 y 3,00, lo que suma 4,00

Entrada:  N = 5, arr[] = {1, 2, 3, 4, 5}
Salida: 7.50
Explicación: Dado que hay 5 elementos en la array, divida la array como {1, 2, 3, 4} y { 5}. 
Sus tamaños son 4 y 1 respectivamente. La media del primer subconjunto será (1+2+3+4)/4 = 2,50 
y la media del otro subconjunto será 5. Por lo tanto, la suma de las medias será 2,50+5,00 = 7,50
Para cualquier otra división del subconjunto, la la suma de las medias no será superior a 7,50. 
Ejemplos: {1, 2, 3} y {4, 5} los medios serán (1+2+3)/3 y (4+5)/2 
que es 2.00 y 4.50 respectivamente que suma 6.50 que es menor que 7.50

Enfoque: la tarea se puede resolver usando algunas observaciones. Se puede observar que la suma máxima de medias de 2 subconjuntos no vacíos se puede lograr si uno de los subconjuntos contiene solo el elemento máximo y el otro subconjunto contiene el resto de los elementos.

A continuación se muestra la implementación del enfoque anterior: 

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the maximum sum of the
// mean of the sum of two subsets of an array
double maxMeanSubsetSum(int arr[], int N)
{
    // Sorting the array
    sort(arr, arr + N);
 
    // Stores the sum of array
    double sum = 0;
 
    // Loop through the array and store
    // sum of elements except the largest
    for (int i = 0; i < N - 1; i++) {
        sum += arr[i];
    }
 
    // Calculating the mean
    sum = sum / (N - 1);
 
    // Adding the largest number
    // to the calculated mean
    sum += arr[N - 1];
    return sum;
}
 
// Driver code
int main()
{
    int arr[] = { 1, 2, 3, 4, 5 };
    int N = 5;
 
    // Giving output correct to
    // two decimal places
    cout << setprecision(2) << fixed
         << maxMeanSubsetSum(arr, N);
    return 0;
}

// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
 
class GFG {
 
  // Function to return the maximum sum of the
  // mean of the sum of two subsets of an array
  static double maxMeanSubsetSum(int arr[], int N)
  {
     
    // Sorting the array
    Arrays.sort(arr);
 
    // Stores the sum of array
    double sum = 0;
 
    // Loop through the array and store
    // sum of elements except the largest
    for (int i = 0; i < N - 1; i++) {
      sum += arr[i];
    }
 
    // Calculating the mean
    sum = sum / (N - 1);
 
    // Adding the largest number
    // to the calculated mean
    sum += arr[N - 1];
    return sum;
  }
 
  // Driver code
  public static void main (String[] args) {
    int arr[] = { 1, 2, 3, 4, 5 };
    int N = 5;
 
    // Giving output correct to
    // two decimal places
    System.out.print(String.format("%.2f", maxMeanSubsetSum(arr, N)));
  }
}
 
// This code is contributed by hrithikgarg03188.

# Python code for the above approach
 
# Function to return the maximum sum of the
# mean of the sum of two subsets of an array
def maxMeanSubsetSum(arr, N):
 
    # Sorting the array
    arr.sort()
 
    # Stores the sum of array
    sum = 0
 
    # Loop through the array and store
    # sum of elements except the largest
    for i in range(N - 1):
        sum += arr[i]
 
    # Calculating the mean
    sum = sum / (N - 1)
 
    # Adding the largest number
    # to the calculated mean
    sum = sum + arr[N - 1]
    return sum
 
# Driver code
arr = [1, 2, 3, 4, 5]
N = 5
 
# Giving output correct to
# two decimal places
print("{0:.2f}".format(maxMeanSubsetSum(arr, N)))
 
# This code is contributed by Potta Lokesh

// C# program for the above approach
using System;
 
public class GFG
{
 
  // Function to return the maximum sum of the
  // mean of the sum of two subsets of an array
  static double maxMeanSubsetSum(int[] arr, int N)
  {
 
    // Sorting the array
    Array.Sort(arr);
 
    // Stores the sum of array
    double sum = 0;
 
    // Loop through the array and store
    // sum of elements except the largest
    for (int i = 0; i < N - 1; i++) {
      sum += arr[i];
    }
 
    // Calculating the mean
    sum = sum / (N - 1);
 
    // Adding the largest number
    // to the calculated mean
    sum += arr[N - 1];
    return sum;
  }
 
  // Driver Code
  public static void Main(String[] args)
  {
    int[] arr = { 1, 2, 3, 4, 5 };
    int N = 5;
 
    // Giving output correct to
    // two decimal places
    Console.Write(string.Format("{0:0.00}", maxMeanSubsetSum(arr, N)));
  }
}
 
// This code is contributed by code_hunt.

<script>
    // JavaScript program for the above approach
 
    // Function to return the maximum sum of the
    // mean of the sum of two subsets of an array
    const maxMeanSubsetSum = (arr, N) => {
     
        // Sorting the array
        arr.sort();
 
        // Stores the sum of array
        let sum = 0;
 
        // Loop through the array and store
        // sum of elements except the largest
        for (let i = 0; i < N - 1; i++) {
            sum += arr[i];
        }
 
        // Calculating the mean
        sum = sum / (N - 1);
 
        // Adding the largest number
        // to the calculated mean
        sum += arr[N - 1];
        return sum;
    }
 
    // Driver code
    let arr = [1, 2, 3, 4, 5];
    let N = 5;
 
    // Giving output correct to
    // two decimal places
    document.write(parseFloat(maxMeanSubsetSum(arr, N)).toFixed(2));
 
// This code is contributed by rakeshsahni
 
</script>

7.50

Complejidad de tiempo : O(N * logN)
Espacio auxiliar : O(1)