Facebook
From nee, 5 Years ago, written in Plain Text.
Embed
Download Paste or View Raw
Hits: 174
  1.  
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4.  
  5.    
  6. bool ok(vector<int>&arr,int m,int x){
  7.   int cnt=1;
  8.   int i=0;
  9.   int n=arr.size();
  10.   while(cnt<m){
  11.     int next=arr[i]+x;
  12.     int low2=i+1;
  13.     int high2=n-1;
  14.     int ans2=-1;
  15.     while(low2<=high2){
  16.       int mid2=(low2+high2)/2;
  17.       if(arr[mid2]>=next){
  18.         ans=mid2;
  19.         high2=mid2-1;
  20.       }else{
  21.         low2=mid2+1;
  22.       }
  23.     }
  24.     if(ans==-1)return false;
  25.     i=ans;
  26.     cnt++;
  27.   }
  28.  
  29.   if(cnt==m)return true;
  30.   else return false;
  31. }
  32. int findMaximum(vector<int>arr,int m){
  33.   int n=arr.size();
  34.   int low=0;
  35.   int high=1e9;
  36.   int ans=-1;
  37.   while(low<=high){
  38.     int mid=(low+high)/2;
  39.     if(ok(arr,m,mid)){
  40.       ans=mid;
  41.       low=mid+1;
  42.     }else{
  43.       high=mid-1;
  44.     }
  45.   }
  46.  
  47.   return ans;
  48. }
  49. int main()
  50. {
  51.  
  52.   int n;
  53.   cin>>n;
  54.   vector<int>v(n);
  55.   cin>>v;
  56.   int m;
  57.   cin>>m;
  58.   cout<<findMaximum(v,m)<<endl;
  59. }