POJ(PKU) 3258 River Hopscotch

顕著な二分探索。

説明不要な気がする。

#include <cstdio>
#include <algorithm>

using namespace std;

const int INF = 1000000001;
int l,n,m,d[50001]={0};
bool ch(int x){
  int u = 0;
  int pre = 0;
  for(int i = 1;i <= n+1;i++){
    if(d[pre] + x > d[i]){
      u++;
    }else{
      pre = i;
    }
  }
  if(u <= m){
    return true;
  }else{
    return false;
  }
}
  

int main(){

  scanf("%d%d%d",&l,&n,&m);
  
  for(int i = 1;i <= n;i++){
    scanf("%d",&d[i]);
  }
  d[0] = 0;
  d[n+1] = l;
  
  sort(d,d + n + 1);
  
  int lb = -1,ub = INF;

  while(ub - lb > 1){
    int mid = (lb + ub) / 2;
    if(ch(mid)) lb = mid;
    else ub = mid;
  }

  printf("%d\n",lb);
  
  return 0;
  
}