Minimize remaining array element by repeatedly replacing pairs by half of one more than their sum | C ++ program to implement the above approach ; Function to print the smallest element left in the array and the pairs by given operation ; Stores array elements and return the minimum element of arr [ ] in O ( 1 ) ; Stores all the pairs that can be selected by the given operations ; Traverse the array arr [ ] ; Traverse pq while count of elements left in pq greater than 1 ; Stores top element of pq ; Pop top element of pq ; Stores top element of pq ; Pop top element of pq ; Insert ( X + Y + 1 ) / 2 in pq ; Insert the pair ( X , Y ) in pairsArr [ ] ; Print the element left in pq by performing the given operations ; Stores count of elements in pairsArr [ ] ; Print all the pairs that can be selected in given operations ; If i is the first index of pairsArr [ ] ; Print current pairs of pairsArr [ ] ; If i is not the last index of pairsArr [ ] ; If i is the last index of pairsArr [ ] ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; void smallestNumberLeftInPQ ( int arr [ ] , int N ) { priority_queue < int > pq ; vector < pair < int , int > > pairsArr ; for ( int i = 0 ; i < N ; i ++ ) { pq . push ( arr [ i ] ) ; } while ( pq . size ( ) > 1 ) { int X = pq . top ( ) ; pq . pop ( ) ; int Y = pq . top ( ) ; pq . pop ( ) ; pq . push ( ( X + Y + 1 ) / 2 ) ; pairsArr . push_back ( { X , Y } ) ; } cout << " { " << pq . top ( ) << " } , ▁ " ; int sz = pairsArr . size ( ) ; for ( int i = 0 ; i < sz ; i ++ ) { if ( i == 0 ) { cout << " { ▁ " ; } cout << " ( " << pairsArr [ i ] . first << " , ▁ " << pairsArr [ i ] . second << " ) " ; if ( i != sz - 1 ) { cout << " , ▁ " ; } if ( i == sz - 1 ) { cout << " ▁ } " ; } } } int main ( ) { int arr [ ] = { 3 , 2 , 1 } ; int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; smallestNumberLeftInPQ ( arr , N ) ; }