Maximizar la suma del mínimo y máximo de todos los grupos en la distribución

Dada una array arr[] y un número entero N. La tarea es maximizar la suma del mínimo y el máximo de cada grupo en una distribución de los elementos de la array en N grupos donde el tamaño de cada grupo se da en una array b[] de   tamaño N.

Ejemplos:

Entrada: a[] = {17, 12, 11, 9, 8, 8, 5, 4, 3}, N = 3,  
b[] = {2, 3, 4}
Salida: 60
Explicación: Los elementos del arreglo deben distribuirse en grupos {17, 9} {12, 8, 8} {11, 5, 4, 3}.
Entonces la suma se convierte en (17 + 9) + (12 + 8) + (11 + 3) = 26 + 20 + 14 = 60

Entrada: a[] = {12, 3, 4, 2, 5, 9, 8, 1, 2}, N = 3,  
b[] = {1, 4, 4}
Salida: 45

 

Enfoque: este problema se puede resolver utilizando el enfoque codicioso y alguna implementación. Siga los pasos a continuación para resolver el problema dado. 

  • ordenar la array arr[] en orden descendente y b[] en orden ascendente.
  • Inicialice una variable y almacene la salida.
  • Iterar de i = 0 a i = N-1 en el arreglo a[] y agregar cada elemento a ans.
  • Inicialice una variable ind para almacenar el índice de elementos de la array arr[] . Asigne N a la variable ind.
  • Tome un ciclo de i=0 a N-1.
    • Si b[i] > 0 entonces incrementa ind con (b[i]-1) 
    • Agregue arr[ind] a ans , ya que arr[ind] será el elemento más pequeño de ese grupo
    • incrementar ind con 1.
  • salida de la respuesta.

Consulte la siguiente ilustración para una mejor comprensión.

Ilustración:

Considere un ejemplo: arr[] = {17, 12, 11, 9, 8, 8, 5, 4, 3}, N = 3 y b[] = {2, 3, 4}

En primer lugar, ordene la array arr[] en orden descendente y b[] en orden ascendente. Luego, coloque el primer N elemento más grande de la array arr[] en cada grupo como se muestra en la fig.

En segundo lugar, llene cada grupo con el resto del elemento de la array arr[] (un grupo a la vez)

Por lo tanto, la respuesta contendrá la suma de los primeros N elementos de la array arr[]  , es decir, 17, 12, 11 y también el último elemento que se completa en cada grupo, es decir, 9, 8 y 3.

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

C++

// C++ program for above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to maximum possible sum of minimum
// and maximum elements of each group
int geeksforgeeks(int a[], int b[], int n, int k)
{
    // Sorting array a in descending order
    // and array a in ascending order.
    sort(a, a + n, greater<int>());
 
    sort(b, b + k);
 
    // Variable to store the required output.
    int ans = 0;
 
    // Loop to store sum of first k greatest
    // element of array a[] in ans.
    // since they will be gretest element
    // of each group when distributed
    // in group one by one.
    for (int i = 0; i < k; i++) {
        if (b[i] == 1) {
            ans += 2 * a[i];
        }
        else {
            ans += a[i];
        }
 
        --b[i];
    }
    // Variable to store index of element a .
    int ind = k;
 
    // Then after when each grouped is filled,
    // then add a[ind] to ans as a[ind] will be
    // lowest element of each group.
    for (int i = 0; i < k; i++) {
        if (b[i] > 0) {
            ind += b[i] - 1;
            ans += a[ind];
            ind++;
        }
    }
 
    return ans;
}
 
// Driver code
int main()
{
 
    int N = 3;
 
    // Size of array a[]
    int siz = 9;
 
    int a[] = { 17, 12, 11, 9, 8, 8, 5, 4, 3 };
    int b[] = { 2, 3, 4 };
 
    // Function Call
    cout << geeksforgeeks(a, b, 9, N);
}

Java

// Java code to find the maximum median
// of a sub array having length at least K.
import java.util.*;
public class GFG
{
 
// Utility function to sort an array in
// descending order
static void sort(int arr[])
{
    for (int i = 0; i < arr.length; i++)
    {    
        for (int j = i + 1; j < arr.length; j++)
        {    
              if(arr[i] < arr[j])
              {   
                  int temp = arr[i];   
                  arr[i] = arr[j];   
                  arr[j] = temp;   
              }    
        }    
    }   
}
 
// Function to maximum possible sum of minimum
// and maximum elements of each group
static int geeksforgeeks(int a[], int b[], int n, int k)
{
    // Sorting array a in descending order
    // and array b in ascending order.
    sort(a);
 
    Arrays.sort(b);
 
    // Variable to store the required output.
    int ans = 0;
 
    // Loop to store sum of first k greatest
    // element of array a[] in ans.
    // since they will be gretest element
    // of each group when distributed
    // in group one by one.
    for (int i = 0; i < k; i++) {
        if (b[i] == 1) {
            ans += 2 * a[i];
        }
        else {
            ans += a[i];
        }
 
        --b[i];
    }
    // Variable to store index of element a .
    int ind = k;
 
    // Then after when each grouped is filled,
    // then add a[ind] to ans as a[ind] will be
    // lowest element of each group.
    for (int i = 0; i < k; i++) {
        if (b[i] > 0) {
            ind += b[i] - 1;
            ans += a[ind];
            ind++;
        }
    }
 
    return ans;
}
 
// Driver code
public static void main(String args[])
{
    int N = 3;
 
    // Size of array a[]
    int siz = 9;
 
    int a[] = { 17, 12, 11, 9, 8, 8, 5, 4, 3 };
    int b[] = { 2, 3, 4 };
 
    // Function Call
    System.out.println(geeksforgeeks(a, b, 9, N));
}
}
 
// This code is contributed by Samim Hossain Mondal.

Python

# Python program for the above approach
 
# Function to maximum possible sum of minimum
# and maximum elements of each group
def geeksforgeeks(a, b, n, k):
     
    # Sorting array a in descending order
    # and array a in ascending order.
    a.sort(reverse=True)
 
    b.sort()
 
    # Variable to store the required output.
    ans = 0
 
    # Loop to store sum of first k greatest
    # element of array a[] in ans.
    # since they will be gretest element
    # of each group when distributed
    # in group one by one.
    for i in range(0, k):
        if (b[i] == 1):
            ans = ans + (2 * a[i])
         
        else:
            ans = ans + a[i]
 
        b[i] = b[i] - 1
         
    # Variable to store index of element a .
    ind = k
 
    # Then after when each grouped is filled,
    # then add a[ind] to ans as a[ind] will be
    # lowest element of each group.
    for i in range(0, k):
        if (b[i] > 0):
            ind = ind + b[i] - 1
            ans = ans + a[ind]
            ind = ind + 1
 
    return ans
 
# Driver code
N = 3
 
# Size of array a[]
siz = 9;
 
a = [ 17, 12, 11, 9, 8, 8, 5, 4, 3 ]
b = [ 2, 3, 4 ]
 
# Function Call
print(geeksforgeeks(a, b, 9, N))
 
# This code is contributed by Samim Hossain Mondal.

C#

// C# code to find the maximum median
// of a sub array having length at least K.
using System;
public class GFG
{
 
  // Utility function to sort an array in
  // descending order
  static void sort(int[] arr)
  {
    for (int i = 0; i < arr.Length; i++)
    {    
      for (int j = i + 1; j < arr.Length; j++)
      {    
        if(arr[i] < arr[j])
        {   
          int temp = arr[i];   
          arr[i] = arr[j];   
          arr[j] = temp;   
        }    
      }    
    }   
  }
 
  // Function to maximum possible sum of minimum
  // and maximum elements of each group
  static int geeksforgeeks(int[] a, int[] b, int n, int k)
  {
     
    // Sorting array a in descending order
    // and array b in ascending order.
    sort(a);
 
    Array.Sort(b);
 
    // Variable to store the required output.
    int ans = 0;
 
    // Loop to store sum of first k greatest
    // element of array a[] in ans.
    // since they will be gretest element
    // of each group when distributed
    // in group one by one.
    for (int i = 0; i < k; i++) {
      if (b[i] == 1) {
        ans += 2 * a[i];
      }
      else {
        ans += a[i];
      }
 
      --b[i];
    }
    // Variable to store index of element a .
    int ind = k;
 
    // Then after when each grouped is filled,
    // then add a[ind] to ans as a[ind] will be
    // lowest element of each group.
    for (int i = 0; i < k; i++) {
      if (b[i] > 0) {
        ind += b[i] - 1;
        ans += a[ind];
        ind++;
      }
    }
 
    return ans;
  }
 
  // Driver code
  public static void Main()
  {
    int N = 3;
 
    // Size of array a[]
    int siz = 9;
 
    int[] a = { 17, 12, 11, 9, 8, 8, 5, 4, 3 };
    int[] b = { 2, 3, 4 };
 
    // Function Call
    Console.Write(geeksforgeeks(a, b, 9, N));
  }
}
 
// This code is contributed by Saurabh Jaiswal

Javascript

<script>
      // JavaScript code for the above approach
 
      // Function to maximum possible sum of minimum
      // and maximum elements of each group
      function geeksforgeeks(a, b, n, k)
      {
       
          // Sorting array a in descending order
          // and array a in ascending order.
          a.sort(function (a, b) { return b - a })
 
          b.sort(function (a, b) { return a - b })
 
          // Variable to store the required output.
          let ans = 0;
 
          // Loop to store sum of first k greatest
          // element of array a[] in ans.
          // since they will be gretest element
          // of each group when distributed
          // in group one by one.
          for (let i = 0; i < k; i++) {
              if (b[i] == 1) {
                  ans += 2 * a[i];
              }
              else {
                  ans += a[i];
              }
 
              --b[i];
          }
           
          // Variable to store index of element a .
          let ind = k;
 
          // Then after when each grouped is filled,
          // then add a[ind] to ans as a[ind] will be
          // lowest element of each group.
          for (let i = 0; i < k; i++) {
              if (b[i] > 0) {
                  ind += b[i] - 1;
                  ans += a[ind];
                  ind++;
              }
          }
 
          return ans;
      }
 
      // Driver code
      let N = 3;
 
      // Size of array a[]
      let siz = 9;
 
      let a = [17, 12, 11, 9, 8, 8, 5, 4, 3];
      let b = [2, 3, 4];
 
      // Function Call
      document.write(geeksforgeeks(a, b, 9, N));
 
// This code is contributed by Potta Lokesh
  </script>
Producción

60

Complejidad de tiempo: O(M * logM) donde M es el tamaño de la array arr.
Espacio Auxiliar: O(1)

Publicación traducida automáticamente

Artículo escrito por saurabh15899 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *