pastebin

Paste Search Dynamic
Recent pastes
check
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. bool check(int cows, long long pos[], int n, long long distance) {
  5.         int count=1;
  6.         long long last=pos[0];
  7.         for(int i=1;i<n;i++) {
  8.                 if(pos[i]-last>=distance) {
  9.                         last=pos[i];
  10.                         count++;
  11.                 }
  12.                 if(count==cows)
  13.                 {return true;}
  14.         }
  15.         return false;
  16. }
  17.  
  18. int main() {
  19.         int t;
  20.         cin>>t;
  21.         while(t--) {
  22.                 int n,c;
  23.                 cin>>n>>c;
  24.                 long long pos[n];
  25.                 for(int i=0;i<n;i++) {
  26.                         cin>>pos[i];
  27.                 }
  28.                 sort(pos,pos+n);
  29.                 long long start=0;
  30.                 long long end=pos[n-1]-pos[0];
  31.                 long long ans=-1;
  32.                 while(start<=end) {
  33.                         long long mid=start+(end-start)/2;
  34.                         if(check(c,pos,n,mid)) {
  35.                                 ans=mid;
  36.                                 start=mid+1;
  37.                         }
  38.                         else {
  39.                                 end=mid-1;
  40.                         }
  41.                 }
  42.                 cout<<ans<<endl;
  43.         }
  44.        
  45. }
Parsed in 0.007 seconds