Suma de los máximos de array después de K operaciones al reducir el elemento máximo a la mitad

Dada una array arr[] de N enteros y un entero K , la tarea es encontrar la suma del máximo posible de la array en la que cada operación reemplaza el máximo actual de la array con su mitad.

Ejemplo:

Entrada: arr[] = {2, 4, 6, 8, 10}, K = 5
Salida: 33
Explicación: En la primera operación, el máximo de la array dada es 10. Por lo tanto, el valor se convierte en 10 y la array después de la primera la operación se convierte en arr[] = {2, 4, 6, 8, 5}. 
El valor después de la segunda operación = 18 y arr[] = {2, 4, 6, 4, 5}. 
De manera similar, avanzando, el valor después de la quinta operación será 33.

Entrada: arr[] = {6, 5}, K = 3
Salida: 14

Enfoque: el problema dado se puede resolver con la ayuda de un enfoque codicioso . La idea es utilizar una estructura de datos de pila máxima . Por lo tanto, recorra la array dada e inserte todos los elementos de la array arr[] en una cola de máxima prioridad . En cada operación, elimine el máximo del montón usando la operación pop, agréguelo al valor y vuelva a insertar el valor después de dividirlo por dos en el montón. El valor después de repetir la operación anterior K veces es la respuesta requerida.

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 maximum possible
// value after K given operations
int maxValue(vector<int> arr, int K)
{
    // Stores required value
    int val = 0;
 
    // Initializing priority queue
    // with all elements of array
    priority_queue<int> pq(arr.begin(),
                           arr.end());
 
    // Loop to iterate through
    // each operation
    while (K--) {
 
        // Current Maximum
        int max = pq.top();
        pq.pop();
 
        // Update value
        val += max;
 
        // Reinsert maximum
        pq.push(max / 2);
    }
 
    // Return Answer
    return val;
}
 
// Driver Call
int main()
{
    vector<int> arr = { 2, 4, 6, 8, 10 };
    int K = 5;
    cout << maxValue(arr, K);
}

// Java code for the above approach
import java.util.Comparator;
import java.util.PriorityQueue;
class CustomComparator implements Comparator<Integer> {
 
  @Override
  public int compare(Integer number1, Integer number2)
  {
    int value =  number1.compareTo(number2);
 
    // elements are sorted in reverse order
    if (value > 0) {
      return -1;
    }
    else if (value < 0) {
      return 1;
    }
    else {
      return 0;
    }
  }
}
class GFG {
 
  // Function to find maximum possible
  // value after K given operations
  static int maxValue(int[] arr, int K)
  {
 
    // Stores required value
    int val = 0;
 
    // Initializing priority queue
    // with all elements of array
    PriorityQueue<Integer> pq
      = new PriorityQueue<Integer>(new CustomComparator());
 
    for (int i = 0; i < arr.length; i++) {
      pq.add(arr[i]);
    }
 
    // Loop to iterate through
    // each operation
    while (K != 0) {
 
      // Current Maximum
      int max = pq.poll();
 
      // Update value
      val += max;
 
      // Reinsert maximum
      pq.add((int)Math.floor(max / 2));
      K = K - 1;
    }
 
    // Return Answer
    return val;
  }
 
  // Driver Call
  public static void main(String[] args)
  {
    int[] arr = { 2, 4, 6, 8, 10 };
    int K = 5;
    System.out.println(maxValue(arr, K));
  }
}
 
// This code is conbtributed by Potta Lokesh

# python3 program of the above approach
from queue import PriorityQueue
 
# Function to find maximum possible
# value after K given operations
def maxValue(arr, K):
 
    # Stores required value
    val = 0
 
    # Initializing priority queue
    # with all elements of array
    pq = PriorityQueue()
 
    for dt in arr:
        pq.put(-1*dt)
 
    # Loop to iterate through
    # each operation
    while (True):
 
        # Current Maximum
        max = -1 * pq.get()
 
        # Update value
        val += max
 
        # Reinsert maximum
        pq.put(-1 * (max // 2))
 
        K -= 1
 
        if K == 0:
            break
 
    # Return Answer
    return val
 
# Driver Call
if __name__ == "__main__":
 
    arr = [2, 4, 6, 8, 10]
    K = 5
    print(maxValue(arr, K))
 
    # This code is contributed by rakeshsahni

33

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