sajid161

18:2

May 9th, 2021
585
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2. #define optimize() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  3. using namespace std;
  4. bool check(int a,vector<int>v,int k)
  5. {
  6.         int last=v[0]+a;
  7.         k--;
  8.         for( int i=1;i<v.size();i++)
  9.         {
  10.            if(abs(v[i]-last)>a)
  11.            {
  12.                if(k==0) return 0;
  13.                last=v[i]+a;
  14.                k--;
  15.            }
  16.         }
  17.      return 1;
  18.  
  19. }
  20. int main()
  21. {
  22.     optimize();
  23.     int t;
  24.     cin>>t;
  25.     for(int tc=1;tc<=t;tc++)
  26.     {
  27.         int n,m,k;
  28.         cin>>n>>m>>k;
  29.         vector<int>v(m);
  30.         for(int i=0;i<m;i++) cin>>v[i];
  31.         int l=0,r=n,ans;
  32.         while(l<=r)
  33.         {
  34.             int mid=(l+r)/2;
  35.             if(check(mid,v,k))
  36.             {
  37.                 ans=mid;
  38.                 r=mid-1;
  39.             }
  40.             else l=mid+1;
  41.         }
  42.         cout<<"Case "<<tc<<": "<<ans<<endl;
  43.  
  44.     }
  45. }
  46.  
RAW Paste Data