POJ - 2456 aggressive cows

Title Description

Farmer John  Built a long corral , It includes N (2 ≤ N ≤ 100,000) Compartments , The compartments are numbered in turn x1,…,xN(0 ≤ xi ≤ 1,000,000,000). however ,John  Of C(2 ≤ C ≤ N) The cows don't like this layout , And a few cows in a cubicle , They're going to fight . In order not to let cattle hurt each other .John  Decide to allocate compartments to the cattle , Make the minimum distance between any two cows as large as possible , that , What is the maximum value of this minimum distance ？

Input format

first line ： Two integers separated by spaces N  and C ;

The second line --- The first N+1  That's ok ：i+1  The line points out xi The location of .

Output format

An integer , Maximum value of minimum distance .

sample input

5 3
1 2 8 4 9

sample output

3

Sample explanation

Put the cow in 1,4,8 So the minimum distance is 3.

The code is as follows ：

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
int n, m;
const int N = 1e5 + 10;
int a[N];

bool c(int x) {
   int last = 0; // Initialize to the subscript of the position of the first cowshed 
   for(int i = 1; i < m; i ++) { 
// i from 1 Start judging , Not from 0 Start , Because I compared the first cowshed with the second cowshed at the beginning 
      int crt = last + 1;
      while(crt < n && a[crt] - a[last] < x) {
         crt ++;
      }
      if(crt == n)   return false;// At this time, the cowshed has been used up , But the cow hasn't finished yet , So failure 
      last = crt; //  When a[crt] - a[last] >= x, When it shows that you can put down a cow , take last Updated to crt
   }
   return true; //  When all the cattle can be released , Show success , return true
}

void solve() {
   sort(a, a + n);
   int l = 0, r = a[n - 1] - a[0];
   int mid;
   while(l < r) {     // Standard bisection template 
      mid = (l + r) >> 1;
      if(c(mid))  l = mid + 1; //  Analyze, judge and choose according to the specific situation 
      else r = mid;
   }
   cout << l - 1;
/*
 Suppose the last answer is true mid, here l = mid + 1 , Then the next one must not be established and l = r sign out ,
 The answer is l - 1
*/
}

int main()
{
   scanf("%d %d", &n, &m);
   for(int i = 0; i < n; i ++)    scanf("%d", &a[i]);
   solve();

   return 0;
}