Minimice el costo dividiendo el Array dado en subconjuntos de tamaño K y agregando los elementos K/2 más altos de cada subconjunto al costo

Dada una array arr[] de N enteros y un entero K , la tarea es calcular el costo mínimo al dividir los elementos de la array en subconjuntos de tamaño K y agregar los ⌈K/2⌉ elementos máximos al costo.

Nota: ⌈K/2⌉ significa valor máximo de K/2.

Ejemplos:

Entrada: arr[] = {1, 1, 2, 2}, K = 2
Salida: 3
Explicación: Los elementos de array dados se pueden dividir en subconjuntos {2, 2} y {1, 1}. 
Por tanto, el coste será 2 + 1 = 3, que es el mínimo posible. 

Entrada: arr[] = {1, 2, 3, 4, 5, 6}, K = 3
Salida: 16
Explicación: La array se puede dividir como {1, 2, 3} y {4, 5, 6}.
Ahora ceil(3/2) = ceil(1.5) = 2.
Así que toma los 2 elementos más altos de cada conjunto. 
La suma se convierte en 2 + 3 + 5 + 6 = 16

Enfoque: el problema dado se puede resolver utilizando un enfoque codicioso . La idea es ordenar los elementos en orden decreciente y comenzar a formar los grupos de K elementos consecutivamente y mantener la suma de los ⌈K/2⌉ elementos más altos de cada grupo en una variable. De esta forma se conseguirá que los elementos cuyo coste no se tenga en cuenta sean los máximos posibles y por tanto se minimice el coste global de los elementos seleccionados.

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

// C++ program of the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find minimum cost by splitting
// the array into subsets of size at most K
// and adding maximum K/2 elements into cost
int minimizeCost(vector<int> arr, int K)
{
    // Stores the final cost
    int ans = 0;
 
    // Sort the array arr[]
    sort(arr.begin(), arr.end(),
         greater<int>());
 
    // Loop to iterate over each
    // group of K elements
    for (int i = 0; i < arr.size();
         i += K) {
 
        // Loop to iterate over
        // maximum K/2 elements
        for (int j = i; j < i + ceil(K / 2.0)
                        && j < arr.size();
             j++) {
            ans += arr[j];
        }
    }
 
    // Return Answer
    return ans;
}
 
// Driver code
int main()
{
    vector<int> arr = { 1, 2, 3, 4, 5, 6 };
    int K = 3;
 
    cout << minimizeCost(arr, K);
    return 0;
}

// JAVA program of the above approach
import java.util.*;
class GFG
{
   
    // Function to find minimum cost by splitting
    // the array into subsets of size at most K
    // and adding maximum K/2 elements into cost
    public static int minimizeCost(ArrayList<Integer> arr,
                                   int K)
    {
        // Stores the final cost
        int ans = 0;
 
        // Sort the array arr[]
        Collections.sort(arr, Collections.reverseOrder());
 
        // Loop to iterate over each
        // group of K elements
        for (int i = 0; i < arr.size(); i += K) {
 
            // Loop to iterate over
            // maximum K/2 elements
            for (int j = i; j < i + Math.ceil(K / 2.0)
                            && j < arr.size();
                 j++) {
                ans += arr.get(j);
            }
        }
 
        // Return Answer
        return ans;
    }
 
    // Driver code
    public static void main(String[] args)
    {
        ArrayList<Integer> arr = new ArrayList<>(
            Arrays.asList(1, 2, 3, 4, 5, 6));
        int K = 3;
        System.out.print(minimizeCost(arr, K));
    }
}
 
// This code is contributed by Taranpreet

# Pyhton program of the above approach
import math
 
#  Function to find minimum cost by splitting
#  the array into subsets of size at most K
#  and adding maximum K/2 elements into cost
def minimizeCost(arr, K):
     
    # Stores the final cost
    ans = 0
 
    # Sort the array arr[]
    arr.sort(reverse = True)
 
    # Loop to iterate over each
    # group of K elements
    i = 0
    while(i < len(arr)):
 
        # Loop to iterate over
        # maximum K/2 elements
        j = i
        while(j < i + math.ceil(K / 2.0) and j < len(arr)):
             
            ans += arr[j]
            j += 1
             
        i += K
 
    # Return Answer
    return ans
 
# Driver code
arr = [ 1, 2, 3, 4, 5, 6 ]
K = 3
 
print(minimizeCost(arr, K))
 
# This code is contributed by samim2000.

// C# implementation of the above approach
using System;
using System.Collections.Generic;
 
class GFG{
 
  // Function to find minimum cost by splitting
  // the array into subsets of size at most K
  // and adding maximum K/2 elements into cost
  static int minimizeCost(List<int> arr, int K)
  {
    // Stores the final cost
    int ans = 0;
 
    // Sort the array arr[]
    arr.Sort((a, b) => b - a);
 
    // Loop to iterate over each
    // group of K elements
    for (int i = 0; i < arr.Count;
         i += K) {
 
      // Loop to iterate over
      // maximum K/2 elements
      for (int j = i; j < i + Math.Ceiling(K / 2.0)
           && j < arr.Count;
           j++) {
        ans += arr[j];
      }
    }
 
    // Return Answer
    return ans;
  }
 
  // Driver Code
  public static void Main()
  {
    List<int> arr = new List<int>{ 1, 2, 3, 4, 5, 6 };
    int K = 3;
 
    Console.Write(minimizeCost(arr, K));
  }
}
 
// This code is contributed by sanjoy_62.

<script>
       // JavaScript code for the above approach
 
       // Function to find minimum cost by splitting
       // the array into subsets of size at most K
       // and adding maximum K/2 elements into cost
       function minimizeCost(arr, K)
       {
        
           // Stores the final cost
           let ans = 0;
 
           // Sort the array arr[]
           arr.sort(function (a, b) { return b - a })
 
           // Loop to iterate over each
           // group of K elements
           for (let i = 0; i < arr.length;
               i += K) {
 
               // Loop to iterate over
               // maximum K/2 elements
               for (let j = i; j < i + Math.ceil(K / 2.0)
                   && j < arr.length;
                   j++) {
                   ans += arr[j];
               }
           }
 
           // Return Answer
           return ans;
       }
 
       // Driver code
       let arr = [1, 2, 3, 4, 5, 6];
       let K = 3;
 
       document.write(minimizeCost(arr, K));
 
      // This code is contributed by Potta Lokesh
   </script>

16

Complejidad de tiempo: O(N*log N)
Espacio auxiliar: O(1)