Cut the Bamboo| CUTBAMBOO

editorial
1

Problem Link

Cut the Bamboo

Setter: Ayush Kumar
Tester: Ramandeep Singh
Editorialist: Ayush Kumar

Difficulty

Medium

problem

Devansham Upadhyay, the King of Bamboo Forest, wants some bamboo for the winter season. He doesn’t like the cutting of forest but also needs some Bamboo. He needs a collection of K Bamboo and has asked you to cut all the Bamboo at maximum height H from the ground to satisfy the requirement. You will be provided with an array of size N containing the list of heights of Bamboo as h1, h2, ...hn. Find that maximum height H.

Explanation

As we can observe by looking into its constrain which is <= 10^18 and there is a monotonic function form like for height h from 0 to 1e18, this is a binary search problem.

The results of the monotonic function look something like (F :-> false) (T:-> true) T T T T T T T T T T T T T T T T T T F F F F F F F F F F F F F F F F F

we have to find the last height h at which our function gives us true.

Time Complexity

O(n x log(n))

Solution

#include<bits/stdc++.h>
using namespace std;
#define int long long int
int n,k;
int a[1000000];

bool check(int m,int k)
{
   int sum =0;
   for(int i=1;i<=n;i++)
   {
     if(a[i]>m)
     {
       sum += (a[i]-m);
     }
   }

   if(sum>=k){
      return true;
   }
   return false;
}

void solve()
{
   // n<=10^6
   cin>>n>>k; //      k<= 10^18
   for(int i=1;i<=n;i++)
   {
      cin>>a[i];
   }
   int lo = 0,hi = 1e18,mid;
   while(hi-lo>1)
   {
      mid = lo + (hi-lo)/2;
      if(check(mid,k))
      {
         lo =  mid;
      }      
      else
      {
         hi = mid-1;
      }
   }
   if(check(hi,k))
   {
      cout<<hi;
   }
   else{
      cout<<lo;
   }
}
int32_t main()
{
   ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    solve();
   return 0;
}