Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- bool check(vector<int> &a,int n,int h,int mid){
- for(int i=1;i<n;i++){
- h-=min(a[i]-a[i-1],mid);
- if(h<=0)return true;
- }
- if(h<=mid)return true;
- return false;
- }
- int minimumJugCapacity(int N,int H,vector<int> &A){
- int start =1;
- int end = H;
- int ans = 0;
- while(start<=end){
- int mid = (start+end)/2;
- if(check(A,N,H,mid)){
- ans = mid;
- end = mid-1;
- }
- else{
- start = mid+1;
- }
- }
- return ans;
- }
- int main(){
- int t;
- cin>>t;
- while(t--){
- int N,H;
- cin>>N>>H;
- vector<int> A(N);
- for(int i=0;i<N;i++)cin>>A[i];
- cout<<minimumJugCapacity(N,H,A)<<endl;
- }
- }
Add Comment
Please, Sign In to add comment