Divida la array en K subconjuntos para maximizar la suma de sus segundos elementos más grandes

Dada una array arr[] que consta de N enteros y un entero K , la tarea es dividir la array en K subconjuntos ( N % K = 0 ) de modo que se maximice la suma de los segundos elementos más grandes de todos los subconjuntos.

Ejemplos:

Entrada: arr[]={1, 3, 1, 5, 1, 3}, K = 2
Salida: 4
Explicación: Dividir la array en los subconjuntos {1, 1, 3} y {1, 3, 5} maximiza la suma de los segundos elementos máximos en las dos arrays.

Entrada: arr[] = {1, 2, 5, 8, 6, 4, 3, 4, 9}, K = 3
Salida: 17

Enfoque: la idea es ordenar la array y seguir agregando cada segundo elemento encontrado mientras se recorre la array en sentido inverso, comenzando desde el segundo elemento más grande de la array , exactamente K veces. Siga los pasos a continuación para resolver el problema:

• Ordene la array en orden ascendente .
• Recorre la array arr[] al revés.
• Inicializa el i = N – 1 .
• Iterar K veces y agregar arr[i – 1] a la suma y reducir i por 2 .
• Finalmente, imprime la suma obtenida.

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

// C++ program to implement
// the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to split array into
// K subsets having maximum
// sum of their second maximum elements
void splitArray(int arr[], int n, int K)
{
    // Sort the array
    sort(arr, arr + n);
 
    int i = n - 1;
 
    // Stores the maximum possible
    // sum of second maximums
    int result = 0;
 
    while (K--) {
 
        // Add second maximum
        // of current subset
        result += arr[i - 1];
 
        // Proceed to the second
        // maximum of next subset
        i -= 2;
    }
 
    // Print the maximum
    // sum obtained
    cout << result;
}
 
// Driver Code
int main()
{
    // Given array arr[]
    int arr[] = { 1, 3, 1, 5, 1, 3 };
 
    // Size of array
    int N = sizeof(arr)
            / sizeof(arr[0]);
 
    int K = 2;
 
    // Function Call
    splitArray(arr, N, K);
 
    return 0;
}

// Java program for the above approach
import java.io.*;
import java.util.Arrays;
   
class GFG
{
   
// Function to split array into
// K subsets having maximum
// sum of their second maximum elements
static void splitArray(int arr[], int n, int K)
{
    // Sort the array
    Arrays.sort(arr);
  
    int i = n - 1;
  
    // Stores the maximum possible
    // sum of second maximums
    int result = 0;
  
    while (K-- != 0)
    {
  
        // Add second maximum
        // of current subset
        result += arr[i - 1];
  
        // Proceed to the second
        // maximum of next subset
        i -= 2;
    }
  
    // Print the maximum
    // sum obtained
    System.out.print(result);
}
   
// Drive Code
public static void main(String[] args)
{
    // Given array arr[]
    int[] arr = { 1, 3, 1, 5, 1, 3 };
  
    // Size of array
    int N = arr.length;
  
    int K = 2;
  
    // Function Call
    splitArray(arr, N, K);
}
}
 
// This code is contributed by sanjoy_62.

# Python3 program to implement
# the above approach
 
# Function to split array into K
# subsets having maximum sum of
# their second maximum elements
def splitArray(arr, n, K):
     
    # Sort the array
    arr.sort()
 
    i = n - 1
 
    # Stores the maximum possible
    # sum of second maximums
    result = 0
 
    while (K > 0):
 
        # Add second maximum
        # of current subset
        result += arr[i - 1]
 
        # Proceed to the second
        # maximum of next subset
        i -= 2
        K -= 1
 
    # Print the maximum
    # sum obtained
    print(result)
 
# Driver Code
if __name__ == "__main__":
 
    # Given array arr[]
    arr = [ 1, 3, 1, 5, 1, 3 ]
 
    # Size of array
    N = len(arr)
 
    K = 2
 
    # Function Call
    splitArray(arr, N, K)
 
# This code is contributed by chitranayal

// C# program for the above approach
using System;
class GFG
{
   
// Function to split array into
// K subsets having maximum
// sum of their second maximum elements
static void splitArray(int []arr, int n, int K)
{
    // Sort the array
    Array.Sort(arr);
  
    int i = n - 1;
  
    // Stores the maximum possible
    // sum of second maximums
    int result = 0;
  
    while (K-- != 0)
    {
  
        // Add second maximum
        // of current subset
        result += arr[i - 1];
  
        // Proceed to the second
        // maximum of next subset
        i -= 2;
    }
  
    // Print the maximum
    // sum obtained
    Console.Write(result);
}
   
// Drive Code
public static void Main(String[] args)
{
    // Given array []arr
    int[] arr = { 1, 3, 1, 5, 1, 3 };
  
    // Size of array
    int N = arr.Length;
  
    int K = 2;
  
    // Function Call
    splitArray(arr, N, K);
}
}
 
// This code is contributed by shikhasingrajput

<script>
 
// JavaScript program to implement
// the above approach
 
// Function to split array into
// K subsets having maximum
// sum of their second maximum elements
function splitArray(arr, n, K)
{
     
    // Sort the array
    arr.sort();
   
    let i = n - 1;
   
    // Stores the maximum possible
    // sum of second maximums
    let result = 0;
   
    while (K-- != 0)
    {
   
        // Add second maximum
        // of current subset
        result += arr[i - 1];
   
        // Proceed to the second
        // maximum of next subset
        i -= 2;
    }
   
    // Print the maximum
    // sum obtained
    document.write(result);
}
 
// Driver code
 
// Given array arr[]
let arr = [ 1, 3, 1, 5, 1, 3 ];
 
// Size of array
let N = arr.length;
 
let K = 2;
 
// Function Call
splitArray(arr, N, K);
 
// This code is contributed by avijitmondal1998
 
</script>

4

Complejidad temporal: O(N logN)
Espacio auxiliar: O(N)