Maximice el costo de vaciar una array dada eliminando repetidamente elementos de la array K

Dada una array , arr[] de tamaño N y un número entero K (N % K = 0) , la tarea es encontrar el costo máximo para eliminar todos los elementos de la array. En cada operación, se pueden eliminar exactamente K elementos de la array y el costo de eliminación es igual al segundo elemento más pequeño eliminado.

Ejemplos:

Entrada: arr[] = { 1, 3, 4, 1, 5, 1, 5, 3 }, K = 4 
Salida: 5 
Explicación: 
eliminando {arr[0], arr[3], arr[5], arr [7]} modifica arr[] a {3, 4, 5, 5}. Segundo elemento más pequeño eliminado = 1. Por lo tanto, costo = 1 
Eliminar {arr[0], arr[1], arr[2], arr[3]} modifica arr[] a {}. Segundo elemento más pequeño eliminado = 4. Por lo tanto, costo = 1 + 4 = 5 
Por lo tanto, la salida requerida es = 5

Entrada: arr[] = { 1, 2, 3, 4}, K = 4 
Salida: 2

Enfoque: el problema se puede resolver utilizando la técnica codiciosa . La idea es ordenar la array y eliminar repetidamente los K elementos de la array más pequeños en cada operación. Siga los pasos a continuación para resolver el problema:

• Inicialice una variable, digamos maxCost , para almacenar el costo máximo para eliminar todos los elementos de la array.
• Ordene la array en orden ascendente .
• Recorra la array usando la variable i y actualice el valor de maxCost = arr[i + 1] e i = i + K .
• Finalmente, imprima el valor de maxCost .

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 find the maximum cost to
// remove all array elements
int maxCostToRemove(int arr[], int N,
                             int K)
{
     
    // Stores maximum cost to
    // remove array elements
    int maxCost = 0;
     
     
    // Sort array in
    // ascending order   
    sort(arr, arr + N);
     
    // Traverse the array
    for (int i = 0; i < N;
                i += K) {
         
        // Update maxCost
        maxCost += arr[i + 1];
    }
     
    return maxCost;
}
 
// Driver Code
int main()
{
    int arr[]= { 1, 3, 4, 1, 5, 1, 5, 3};
    int N = sizeof(arr) / sizeof(arr[0]);
    int K = 4;
    cout<< maxCostToRemove(arr, N, K);
}

// Java program for the above approach
import java.io.*;
import java.util.Arrays;
   
class GFG{
   
// Function to find the maximum cost to
// remove all array elements
static int maxCostToRemove(int arr[], int N,
                             int K)
{
      
    // Stores maximum cost to
    // remove array elements
    int maxCost = 0;
      
      
    // Sort array in
    // ascending order   
    Arrays.sort(arr);
      
    // Traverse the array
    for (int i = 0; i < N;
                i += K) {
          
        // Update maxCost
        maxCost += arr[i + 1];
    }
      
    return maxCost;
}
   
// Drive Code
public static void main(String[] args)
{
    int arr[]= { 1, 3, 4, 1, 5, 1, 5, 3};
    int N = arr.length;
    int K = 4;
    System.out.print(maxCostToRemove(arr, N, K));
}
}
 
// This code is contributed by sanjoy_62

# Python3 program to implement
# the above approach
 
# Function to find the maximum cost to
# remove all array elements
def maxCostToRemove(arr, N, K):
 
    # Stores maximum cost to
    # remove array elements
    maxCost = 0
 
    # Sort array in
    # ascending order
    arr = sorted(arr)
 
    # Traverse the array
    for i in range(0, N, K):
         
        # Update maxCost
        maxCost += arr[i + 1]
 
    return maxCost
 
# Driver Code
if __name__ == '__main__':
    arr= [1, 3, 4, 1, 5, 1, 5, 3]
    N = len(arr)
    K = 4
    print(maxCostToRemove(arr, N, K))
 
# This code is contributed by mohit kumar 29

// C# program for the above approach
using System;
class GFG{
   
// Function to find the maximum cost to
// remove all array elements
static int maxCostToRemove(int []arr, int N,
                             int K)
{
      
    // Stores maximum cost to
    // remove array elements
    int maxCost = 0;
      
      
    // Sort array in
    // ascending order   
    Array.Sort(arr);
      
    // Traverse the array
    for (int i = 0; i < N;
                i += K) {
          
        // Update maxCost
        maxCost += arr[i + 1];
    }
      
    return maxCost;
}
   
// Drive Code
public static void Main(String[] args)
{
    int []arr= { 1, 3, 4, 1, 5, 1, 5, 3};
    int N = arr.Length;
    int K = 4;
    Console.Write(maxCostToRemove(arr, N, K));
}
}
 
// This code is contributed by shikhasingrajput

<script>
 
// Javascript program to implement
// the above approach
 
// Function to find the maximum cost to
// remove all array elements
function maxCostToRemove(arr, N, K)
{
     
    // Stores maximum cost to
    // remove array elements
    let maxCost = 0;
       
    // Sort array in
    // ascending order  
    arr.sort();
       
    // Traverse the array
    for(let i = 0; i < N; i += K)
    {
         
        // Update maxCost
        maxCost += arr[i + 1];
    }
    return maxCost;
}
 
// Driver code
let arr = [ 1, 3, 4, 1, 5, 1, 5, 3 ];
let N = arr.length;
let K = 4;
 
document.write(maxCostToRemove(arr, N, K));
 
// This code is contributed by code_hunt
  
</script>

5

Complejidad temporal: O(N * log N)  
Espacio auxiliar O(1)