Minimizar la suma de los elementos más pequeños de K subsecuencias de longitud L

Dada una array arr[] de tamaño N , la tarea es encontrar la suma mínima posible extrayendo el elemento más pequeño de cualquier K subsecuencias de arr[] de longitud L tal que cada una de las subsecuencias no tenga un elemento compartido. Si no es posible obtener la suma requerida, imprima -1.

Ejemplos: 

Entrada: arr[] = {2, 15, 5, 1, 35, 16, 67, 10}, K = 3, L = 2 Salida: 8 
Explicación : 
tres 
subsecuencias de longitud 2 pueden ser {1, 35}, { 2, 15}, {5, 16} El 
elemento mínimo de {1, 35} es 1. El 
elemento mínimo de {2, 15} es 2. El 
elemento mínimo de {5, 16} es 5. 
Su suma es igual a 8, que es el mínimo posible.

Entrada: arr[] = {19, 11, 21, 16, 22, 18, 14, 12}, K = 3, L = 3 Salida: -1 
Explicación : 
No 
es posible construir 3 subsecuencias de longitud 3 a partir de arr []. 

Enfoque: 
Para optimizar el enfoque anterior, debemos observar los siguientes detalles: 

• Los K elementos más pequeños de la array contribuyen a encontrar la suma mínima de los elementos más pequeños de las K subsecuencias.
• La longitud del arreglo debe ser mayor o igual a (K * L) para formar K subsecuencias de longitud L.

Siga los pasos a continuación para resolver el problema: 

• Compruebe si el tamaño de la array arr[] es mayor que igual a (K * L) .
• Si es así, ordene la array arr[] e imprima la suma de los primeros K elementos de la array después de ordenar.
• De lo contrario, devuelve -1.

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

// C++ Program to find the minimum
// possible sum of the smallest
// elements from K subsequences
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the minimum sum
int findMinSum(int arr[], int K,
               int L, int size)
{
 
    if (K * L > size)
        return -1;
 
    int minsum = 0;
 
    // Sort the array
    sort(arr, arr + size);
 
    // Calculate sum of smallest
    // K elements
    for (int i = 0; i < K; i++)
        minsum += arr[i];
 
    // Return the sum
    return minsum;
}
 
// Driver Code
int main()
{
    int arr[] = { 2, 15, 5, 1,
                  35, 16, 67, 10 };
    int K = 3;
    int L = 2;
 
    int length = sizeof(arr)
                / sizeof(arr[0]);
 
    cout << findMinSum(arr, K,
                       L, length);
 
    return 0;
}

// Java program to find the minimum
// possible sum of the smallest
// elements from K subsequences
import java.util.Arrays;
 
class GFG{
 
// Function to find the minimum sum
static int findMinSum(int []arr, int K,
                      int L, int size)
{
    if (K * L > size)
        return -1;
 
    int minsum = 0;
 
    // Sort the array
    Arrays.sort(arr);
 
    // Calculate sum of smallest
    // K elements
    for(int i = 0; i < K; i++)
        minsum += arr[i];
 
    // Return the sum
    return minsum;
}
 
// Driver Code
public static void main(String args[])
{
    int arr[] = { 2, 15, 5, 1,
                  35, 16, 67, 10 };
    int K = 3;
    int L = 2;
    int length = arr.length;
 
    System.out.print(findMinSum(arr, K,
                                L, length));
}
}
 
// This code is contributed by Ritik Bansal

# Python3 program to find the minimum
# possible sum of the smallest
# elements from K subsequences
 
# Function to find the minimum sum
 
 
def findMinSum(arr, K, L, size):
 
    if (K * L > size):
        return -1
 
    minsum = 0
 
    # Sort the array
    arr.sort()
 
    # Calculate sum of smallest
    # K elements
    for i in range(K):
        minsum += arr[i]
 
    # Return the sum
    return minsum
 
 
# Driver code
if __name__ == '__main__':
 
    arr = [2, 15, 5, 1,
           35, 16, 67, 10]
    K = 3
    L = 2
 
    length = len(arr)
 
    print(findMinSum(arr, K, L, length))
 
# This code is contributed by Shivam Singh

// C# program to find the minimum
// possible sum of the smallest
// elements from K subsequences
using System;
   
class GFG{
   
// Function to find the minimum sum
static int findMinSum(int []arr, int K,
                      int L, int size)
{
    if (K * L > size)
        return -1;
   
    int minsum = 0;
   
    // Sort the array
    Array.Sort(arr); 
   
    // Calculate sum of smallest
    // K elements
    for(int i = 0; i < K; i++)
        minsum += arr[i];
   
    // Return the sum
    return minsum;
}
   
// Driver Code
public static void Main() 
{
    int[] arr = { 2, 15, 5, 1,
                  35, 16, 67, 10 };
    int K = 3;
    int L = 2;
    int length = arr.Length;
   
    Console.Write(findMinSum(arr, K,
                             L, length));
}
}
 
// This code is contributed by code_hunt

<script>
// Javascript program to find the minimum
// possible sum of the smallest
// elements from K subsequences
 
// Function to find the minimum sum
function findMinSum(arr, K, L, size)
{
    if (K * L > size)
        return -1;
 
    let minsum = 0;
 
    // Sort the array
    arr.sort((a, b) => a - b);
 
    // Calculate sum of smallest
    // K elements
    for(let i = 0; i < K; i++)
        minsum += arr[i];
 
    // Return the sum
    return minsum;
}
 
    // Driver Code
     
    let arr = [ 2, 15, 5, 1,
                  35, 16, 67, 10 ];
    let K = 3;
    let L = 2;
    let length = arr.length;
 
   document.write(findMinSum(arr, K,
                                L, length));
 
</script>

8

Complejidad de tiempo: O(N * log(N)) 
Complejidad de espacio: O(1)