Minimize Sum of an Array by at most K reductions | C ++ program to implement the above approach ; Function to obtain the minimum possible sum from the array by K reductions ; Implements the MaxHeap ; Insert elements into the MaxHeap ; Remove the maximum ; Insert maximum / 2 ; Stores the sum of remaining elements ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int minSum ( int a [ ] , int n , int k ) { priority_queue < int > q ; for ( int i = 0 ; i < n ; i ++ ) { q . push ( a [ i ] ) ; } while ( ! q . empty ( ) && k > 0 ) { int top = q . top ( ) / 2 ; q . pop ( ) ; q . push ( top ) ; k -= 1 ; } int sum = 0 ; while ( ! q . empty ( ) ) { sum += q . top ( ) ; q . pop ( ) ; } return sum ; } int main ( ) { int n = 4 ; int k = 3 ; int a [ ] = { 20 , 7 , 5 , 4 } ; cout << ( minSum ( a , n , k ) ) ; return 0 ; }