Samkit5025

Untitled

Sep 15th, 2022
45
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.80 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. bool check(vector<int> &a,int n,int h,int mid){
  5.    
  6.     for(int i=1;i<n;i++){
  7.         h-=min(a[i]-a[i-1],mid);
  8.         if(h<=0)return true;
  9.     }
  10.  
  11.     if(h<=mid)return true;
  12.     return false;
  13. }
  14.  
  15. int minimumJugCapacity(int N,int H,vector<int> &A){
  16.     int start =1;
  17.     int end = H;
  18.     int ans = 0;
  19.     while(start<=end){
  20.         int mid = (start+end)/2;
  21.         if(check(A,N,H,mid)){
  22.             ans = mid;
  23.             end = mid-1;
  24.         }
  25.         else{
  26.             start = mid+1;
  27.         }
  28.     }
  29.     return ans;
  30. }  
  31.  
  32. int main(){
  33.     int t;
  34.     cin>>t;
  35.     while(t--){
  36.         int N,H;
  37.         cin>>N>>H;
  38.  
  39.         vector<int> A(N);
  40.         for(int i=0;i<N;i++)cin>>A[i];
  41.         cout<<minimumJugCapacity(N,H,A)<<endl;
  42.     }
  43. }
Advertisement
Add Comment
Please, Sign In to add comment