Find maximum height to cut all chocolates horizontally such that at least K amount remains | C ++ program for the above approach ; Function to find the sum of remaining chocolate after making the horizontal cut at height mid ; Stores the sum of chocolates ; Traverse the array arr [ ] ; If the height is at least mid ; Return the possible sum ; Function to find the maximum horizontal cut made to all the chocolates such that the sum of the remaining element is at least K ; Ranges of Binary Search ; Perform the Binary Search ; Find the sum of removed after making cut at height mid ; If the chocolate removed is same as the chocolate needed then return the height ; If the chocolate removed is less than chocolate needed then shift to the left range ; Otherwise , shift to the right range ; Return the possible cut ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int cal ( vector < int > arr , int mid ) { int chocolate = 0 ; for ( auto i : arr ) { if ( i >= mid ) chocolate += i - mid ; } return chocolate ; } int maximumCut ( vector < int > arr , int K ) { int low = 0 ; int high = * max_element ( arr . begin ( ) , arr . end ( ) ) ; while ( low <= high ) { int mid = ( low + high ) / 2 ; int chocolate = cal ( arr , mid ) ; if ( chocolate == K ) return mid ; else if ( chocolate < K ) high = mid - 1 ; else { low = mid + 1 ; if ( mid > high ) high = mid ; } } return high ; } int main ( ) { int N = 4 ; int K = 7 ; vector < int > arr { 15 , 20 , 8 , 17 } ; cout << ( maximumCut ( arr , K ) ) ; }