Divida la array en subconjuntos de longitud K para minimizar la suma del segundo elemento más pequeño de cada subconjunto

Dada una array arr[] de tamaño N y un número entero K ( N % K = 0 ), la tarea es dividir la array en subarreglos de tamaño K tal que la suma de los 2 elementos más pequeños de cada ^subarreglo sea la mínima posible.

Ejemplos:

Entrada: arr[] = {11, 20, 5, 7, 8, 14, 2, 17, 16, 10}, K = 5
Salida: 13
Explicación: dividir la array en subconjuntos {11, 5, 14, 2, 10 } y {20, 7, 8, 17, 16} genera la suma mínima de los segundos elementos más pequeños (= 5 + 8 = 13).

Entrada: arr[] = {13, 19, 20, 5, 17, 11, 10, 8, 23, 14}, K = 5
Salida: 19
Explicación: dividir la array en subconjuntos {10, 19, 20, 11, 23 } y {17, 5, 8, 13, 14} genera la suma mínima de los segundos elementos más pequeños (= 11 + 8 = 19).

Enfoque: El problema se puede resolver mediante la técnica de clasificación . Siga los pasos a continuación para resolver este problema:

• Ordena la array dada en orden ascendente .
• Dado que todos los subconjuntos son de K grupos de longitud , elija primero K elementos indexados impares a partir de 1 y calcule su suma.
• Imprime la suma obtenida.

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

// C++ implementation for above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the minimum sum of
// 2nd smallest elements of each subset
int findMinimum(int arr[], int N, int K)
{
    // Sort the array
    sort(arr, arr + N);
 
    // Stores minimum sum of second
    // elements of each subset
    int ans = 0;
 
    // Traverse first K 2nd smallest elements
    for (int i = 1; i < 2 * (N / K); i += 2) {
 
        // Update their sum
        ans += arr[i];
    }
 
    // Print the sum
    cout << ans;
}
 
// Driver Code
int main()
{
    // Given Array
    int arr[] = { 11, 20, 5, 7, 8,
                  14, 2, 17, 16, 10 };
 
    // Given size of the array
    int N = sizeof(arr)
            / sizeof(arr[0]);
 
    // Given subset lengths
    int K = 5;
 
    findMinimum(arr, N, K);
 
    return 0;
}

// Java implementation for the above approach
 
import java.io.*;
import java.util.*;
 
class GFG {
 
    // Function to find the minimum sum of
    // 2nd smallest elements of each subset
    public static void findMinimum(
        int arr[], int N, int K)
    {
        // Sort the array
        Arrays.sort(arr);
 
        // Stores minimum sum of second
        // elements of each subset
        int ans = 0;
 
        // Traverse first K 2nd smallest elements
        for (int i = 1; i < 2 * (N / K); i += 2) {
 
            // Update their sum
            ans += arr[i];
        }
 
        // Print the sum
        System.out.println(ans);
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        // Given Array
        int[] arr = { 11, 20, 5, 7, 8,
                      14, 2, 17, 16, 10 };
 
        // Given length of array
        int N = arr.length;
 
        // Given subset lengths
        int K = 5;
 
        findMinimum(arr, N, K);
    }
}

# Python3 implementation for above approach
 
# Function to find the minimum sum of
# 2nd smallest elements of each subset
def findMinimum(arr, N, K):
   
    # Sort the array
    arr = sorted(arr)
 
    # Stores minimum sum of second
    # elements of each subset
    ans = 0
 
    # Traverse first K 2nd smallest elements
    for i in range(1, 2 * (N//K), 2):
 
        # Update their sum
        ans += arr[i]
 
    # Print the sum
    print (ans)
 
# Driver Code
if __name__ == '__main__':
   
    # Given Array
    arr = [11, 20, 5, 7, 8, 14, 2, 17, 16, 10]
 
    # Given size of the array
    N = len(arr)
 
    # Given subset lengths
    K = 5
    findMinimum(arr, N, K)
 
# This code is contributed by mohit kumar 29

// C# implementation for above approach
using System;
  
class GFG{
  
// Function to find the minimum sum of
// 2nd smallest elements of each subset
public static void findMinimum(int[] arr, int N,
                               int K)
{
     
    // Sort the array
    Array.Sort(arr);
 
    // Stores minimum sum of second
    // elements of each subset
    int ans = 0;
 
    // Traverse first K 2nd smallest elements
    for(int i = 1; i < 2 * (N / K); i += 2)
    {
         
        // Update their sum
        ans += arr[i];
    }
 
    // Print the sum
    Console.WriteLine(ans);
}
 
// Driver Code
public static void Main()
{
     
    // Given Array
    int[] arr = { 11, 20, 5, 7, 8,
                  14, 2, 17, 16, 10 };
 
    // Given length of array
    int N = arr.Length;
 
    // Given subset lengths
    int K = 5;
 
    findMinimum(arr, N, K);
}
}
 
// This code is contributed by susmitakundugoaldanga

<script>
 
// Javascript implementation for
// the above approach
 
    // Function to find the minimum sum of
    // 2nd smallest elements of each subset
    function findMinimum(arr , N , K)
    {
        // Sort the array
        arr.sort((a,b)=>a-b);
 
        // Stores minimum sum of second
        // elements of each subset
        var ans = 0;
 
        // Traverse first K 2nd smallest elements
        for (i = 1; i < 2 * (parseInt(N / K)); i += 2)
        {
 
            // Update their sum
            ans += arr[i];
        }
 
        // Print the sum
        document.write(ans);
    }
 
    // Driver Code
     
        // Given Array
        var arr = [ 11, 20, 5, 7, 8, 14, 2, 17, 16, 10 ];
 
        // Given length of array
        var N = arr.length;
 
        // Given subset lengths
        var K = 5;
 
        findMinimum(arr, N, K);
 
// This code is contributed by todaysgaurav
 
</script>

13

Complejidad de tiempo: O(NlogN)
Complejidad de espacio: O(N)