Máximos de la array cuando el máximo disminuye después de cada acceso

Dado un entero K y una array de enteros arr , la tarea es encontrar el elemento máximo de la array y después de cada recuperación el número se reducirá en 1 . Repita estos pasos exactamente K número de veces e imprima la suma de todos los valores recuperados al final.

Ejemplos: 

Entrada: K = 3, arr[] = {2, 3, 5, 4} 
Salida: 13 
Para K = 1, el máximo actual es 5 (Suma = 5 y arr[] = {2, 3, 4, 4}) 
Para K = 2, el máximo actual es 4 (Suma = 5 + 4 = 9 y arr[] = {2, 3, 3, 4}) 
Para K = 3, el máximo actual es 4 (Suma = 9 + 4 = 13 y arr[] = {2, 3, 3, 3}) 
Por lo tanto, el resultado es 13

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

Enfoque: la idea principal es usar un montón máximo que tendrá el elemento máximo en su raíz en cualquier instancia de tiempo. 

• Cree un montón máximo de todos los elementos de la array.
• Obtenga el elemento raíz del montón y agréguelo a la suma.
• Extraiga el elemento raíz y disminuya en 1 , luego insértelo nuevamente en el montón.
• Repita los dos pasos anteriores exactamente K número de veces.
• Imprime la suma total al final.

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

// C++ implementation of above approach
#include <bits/stdc++.h>
using namespace std;
#define ll long long
 
ll getSum(int arr[], int K, int n)
{
    ll sum = 0;
    priority_queue<ll> maxHeap;
    for (ll i = 0; i < n; i++) {
 
        // put all array elements
        // in a max heap
        maxHeap.push(arr[i]);
    }
 
    while (K--) {
 
        // Get the current maximum element
        ll currentMax = maxHeap.top();
 
        // Add it to the sum
        sum += currentMax;
 
        // Remove the current max from the heap
        maxHeap.pop();
 
        // Add the current max back to the
        // heap after decrementing it by 1
        maxHeap.push(currentMax - 1);
    }
    return sum;
}
 
// driver code
int main()
{
    int arr[] = { 2, 3, 5, 4 }, K = 3;
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << getSum(arr, K, n) << endl;
}

// Java implementation of above approach
import java.util.*;
class Solution
{
 
static int getSum(int arr[], int K, int n)
{
    int sum = 0;
    PriorityQueue<Integer> maxHeap =
                          new PriorityQueue<Integer>(n,Collections.reverseOrder());
    for (int i = 0; i < n; i++) {
 
        // put aint array elements
        // in a max heap
        maxHeap.add(arr[i]);
    }
 
    while (K-->0) {
 
        // Get the current maximum element
        int currentMax = (int)maxHeap.peek();
 
        // Add it to the sum
        sum += currentMax;
 
        // Remove the current max from the heap
        maxHeap.remove();
 
        // Add the current max back to the
        // heap after decrementing it by 1
        maxHeap.add(currentMax - 1);
    }
    return sum;
}
 
// driver code
public static void main(String args[])
{
    int arr[] = { 2, 3, 5, 4 }, K = 3;
    int n =arr.length;
    System.out.println(getSum(arr, K, n));
}
}
//contributed by Arnab Kundu

# Python3 implementation of above approach
# importing the heapq module
import heapq
# function to get maximum sum
 
 
def getSum(arr, K, n):
    Sum = 0
    maxHeap = arr
    # creating a maxheap
    heapq._heapify_max(maxHeap)
    while (K > 0):
        # Get the current maximum element
        currentMax = maxHeap[0]
        # Add it to the sum
        Sum += currentMax
        # decrementing the root of the max heap by 1
        maxHeap[0] -= 1
        # mainaining the heap property
        # as we have reduced the value of root by 1
        # so it may distort the heap property
        heapq._heapify_max(maxHeap)
        K -= 1
    return Sum
 
 
# Driver code
arr = [2, 3, 5, 4]
K = 3
n = len(arr)
print(getSum(arr, K, n))
 
'''This code is contributed by Rajat Kumar'''

// C# implementation of above approach
using System;
using System.Collections.Generic;
class GFG {
  
    static int getSum(int[] arr, int K, int n)
    {
        int sum = 0;
        List<int> maxHeap = new List<int>();
        for (int i = 0; i < n; i++) {
       
            // put all array elements
            // in a max heap
            maxHeap.Add(arr[i]);
        }
         
        maxHeap.Sort();
        maxHeap.Reverse();
         
        while (K-- > 0) {
       
            // Get the current maximum element
            int currentMax = maxHeap[0];
       
            // Add it to the sum
            sum += currentMax;
       
            // Remove the current max from the heap
            maxHeap.RemoveAt(0);
       
            // Add the current max back to the
            // heap after decrementing it by 1
            maxHeap.Add(currentMax - 1);
            maxHeap.Sort();
            maxHeap.Reverse();
        }
        return sum;
    } 
     
  // Driver code
  static void Main()
  {
    int[] arr = { 2, 3, 5, 4 };
    int K = 3;
    int n = arr.Length;
    Console.Write(getSum(arr, K, n));
  }
}
 
// This code is contributed by divyesh072019.

<script>
    // Javascript implementation of above approach
     
    function getSum(arr, K, n)
    {
        let sum = 0;
        let maxHeap = [];
        for (let i = 0; i < n; i++) {
        
            // put all array elements
            // in a max heap
            maxHeap.push(arr[i]);
        }
          
        maxHeap.sort(function(a, b){return a - b});
        maxHeap.reverse();
          
        while (K-- > 0) {
        
            // Get the current maximum element
            let currentMax = maxHeap[0];
        
            // Add it to the sum
            sum += currentMax;
        
            // Remove the current max from the heap
            maxHeap.shift();
        
            // Add the current max back to the
            // heap after decrementing it by 1
            maxHeap.push(currentMax - 1);
            maxHeap.sort(function(a, b){return a - b});
            maxHeap.reverse();
        }
        return sum;
    }
     
    // Driver code
    let arr = [ 2, 3, 5, 4 ];
    let K = 3;
    let n = arr.length;
    document.write(getSum(arr, K, n));
     
    // This code is contributed by suresh07.
</script>

13