Minimice la suma de una array en la mayoría de las reducciones K

Dada una array de enteros arr[] que consta de N enteros, la tarea es minimizar la suma de la array dada realizando como máximo K operaciones, donde cada operación implica reducir un elemento de la array arr[i] a floor(arr[i] /2) .

Ejemplos:

Entrada: N = 4, a[] = {20, 7, 5, 4}, K = 3 
Salida: 17 
Explicación: 
Operación 1: {20, 7, 5, 4} -> {10, 7, 5, 4 } 
Operación 2: {10, 7, 5, 4} -> {5, 7, 5, 4} 
Operación 3: {5, 7, 5, 4} -> {5, 3, 5, 4} 
Ninguna operación más puede ser llevado a cabo. Por lo tanto, suma de la array = 17.

Entrada: N = 4, a[] = {10, 4, 6, 16}, K = 2 
Salida: 23

Enfoque: Para obtener la suma mínima posible, la idea principal para cada operación es reducir el elemento máximo en la array antes de cada operación. Esto se puede implementar usando MaxHeap . Siga los pasos a continuación para resolver el problema:

• Inserte todos los elementos de la array en MaxHeap .
• Extraiga la raíz de MaxHeap e inserte (elemento extraído) / 2 en MaxHeap
• Después de repetir el paso anterior K veces, extraiga los elementos del MaxHeap uno por uno y siga agregando sus valores. Finalmente, imprima la suma.

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 obtain the minimum possible
// sum from the array by K reductions
int minSum(int a[], int n, int k)
{
    priority_queue <int> q;
     
    // Insert elements into the MaxHeap
    for(int i = 0; i < n; i++)
    {
        q.push(a[i]);
    }
     
    while(!q.empty() && k > 0)
    {
        int top = q.top() / 2;
         
        // Remove the maximum            
        q.pop();
         
        // Insert maximum / 2
        q.push(top);
        k -= 1;
    }
     
    // Stores the sum of remaining elements
    int sum = 0;
    while(!q.empty())
    {
        sum += q.top();
        q.pop();
    }
    return sum;
}
 
// Driver code
int main()
{
    int n = 4;
    int k = 3;
    int a[] = { 20, 7, 5, 4 };
         
    cout << (minSum(a, n, k));
     
    return 0;
}
 
// This code is contributed by jojo9911

// Java Program to implement the
// above approach
import java.io.*;
import java.util.*;
class GFG {
 
    // Function to obtain the minimum possible
    // sum from the array by K reductions
    public static int minSum(int a[], int n, int k)
    {
        // Implements the MaxHeap
        PriorityQueue<Integer> maxheap
            = new PriorityQueue<>((one, two) -> two - one);
 
        // Insert elements into the MaxHeap
        for (int i = 0; i < n; i++)
            maxheap.add(a[i]);
 
        while (maxheap.size() > 0 && k > 0) {
 
            // Remove the maximum
            int max_ele = maxheap.poll();
 
            // Insert maximum / 2
            maxheap.add(max_ele / 2);
            k -= 1;
        }
 
        // Stores the sum of remaining elements
 
        int sum = 0;
        while (maxheap.size() > 0)
            sum += maxheap.poll();
 
        return sum;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int n = 4;
        int k = 3;
        int a[] = { 20, 7, 5, 4 };
        System.out.println(minSum(a, n, k));
    }
}

# Python3 program to implement the
# above approach
 
# Function to obtain the minimum possible
# sum from the array by K reductions
def minSum(a, n, k):
     
    q = []
     
    # Insert elements into the MaxHeap
    for i in range(n):
        q.append(a[i])
         
    q = sorted(q)   
 
    while (len(q) > 0 and k > 0):
        top = q[-1] // 2
 
        # Remove the maximum
        del q[-1]
 
        # Insert maximum / 2
        q.append(top)
        k -= 1
        q = sorted(q)
 
    # Stores the sum of remaining elements
    sum = 0
    while(len(q) > 0):
        sum += q[-1]
        del q[-1]
         
    return sum
 
# Driver code
if __name__ == '__main__':
     
    n = 4
    k = 3
     
    a = [ 20, 7, 5, 4 ]
 
    print(minSum(a, n, k))
 
# This code is contributed by mohit kumar 29

// C# program to implement the
// above approach
using System;
using System.Collections.Generic;
 
class GFG{
     
// Function to obtain the minimum possible
// sum from the array by K reductions
static int minSum(int[] a, int n, int k)
{
     
    // Implements the MaxHeap
    List<int> q = new List<int>();
    for(int i = 0; i < n; i++)
    {
         
        // Insert elements into the MaxHeap
        q.Add(a[i]);
    }
     
    q.Sort();
    while (q.Count != 0 && k > 0)
    {
        int top = q[q.Count - 1] / 2;
         
        // Remove the maximum
        // Insert maximum / 2
        q[q.Count - 1] = top;
         
        k--;
        q.Sort();
    }
     
    // Stores the sum of remaining elements
    int sum = 0;
    while (q.Count != 0)
    {
        sum += q[0];
        q.RemoveAt(0);
    }
    return sum;
}
 
// Driver Code
static public void Main()
{
    int n = 4;
    int k = 3;
    int[] a = { 20, 7, 5, 4 };
     
    Console.WriteLine(minSum(a, n, k));
}
}
 
// This code is contributed by avanitrachhadiya2155

<script>
// Javascript Program to implement the
// above approach
 
// Function to obtain the minimum possible
    // sum from the array by K reductions
function  minSum(a,n,k)
{
    // Implements the MaxHeap
        let maxheap = [];
  
        // Insert elements into the MaxHeap
        for (let i = 0; i < n; i++)
            maxheap.push(a[i]);
          
        maxheap.sort(function(a,b){return a-b;});
         
        while (maxheap.length > 0 && k > 0) {
  
            // Remove the maximum
            let max_ele = maxheap.pop();
  
            // Insert maximum / 2
            maxheap.push(Math.floor(max_ele / 2));
            k -= 1;
            maxheap.sort(function(a,b){return a-b;});
        }
  
        // Stores the sum of remaining elements
  
        let sum = 0;
        while (maxheap.length > 0)
            sum += maxheap.shift();
  
        return sum;
}
 
// Driver Code
let n = 4;
let k = 3;
let a = [ 20, 7, 5, 4 ];
document.write(minSum(a, n, k));
 
// This code is contributed by unknown2108
</script>

17

Complejidad temporal: O(Klog(N)) 
Espacio auxiliar: O(N)