POJ 2456 Aggressive cows

binary search poj

解説
蟻本に書いてある。

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

const int INF = 1 << 29;

int n,m,a;
vector<int> x;

bool C(int d){
  int last = 0;
  for(int i = 1; i < m; i++){
    int crt = last + 1;
    while(crt < n && x[crt] - x[last] < d) crt++;
    if(crt == n) return false;
    last = crt;
  }
  return true;
}

int main(){
  cin >> n >> m;
  for(int i = 0; i < n; i++){
    cin >> a;
    x.push_back(a);
  }
  sort(x.begin(),x.end());
  
  int l = 0, r = INF;
  
  while( r - l > 1 ){
    int mid = (r + l) / 2;
    if(C(mid)) l = mid;
    else r = mid;
  }
  
  cout << l << endl;
}