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 = 60Entrada: 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