POJ.3258 River Hopscotch

1.Problem
http://poj.org/problem?id=3258

2.Idea
Binary Search

3.Source

 int L, N, M;  
 int x[50005];  
 bool C(int d)  
 {  
      int cnt = 0;  
      int last = 0;  
      for (int i = 1; i <= N + 1; i++) {  
           if (x[i] - x[last] < d) {  
                cnt++;  
           }  
           else {  
                last = i;  
           }  
      }  
      if (cnt <= M) return true;  
      else return false;  
 }  
 void solve()  
 {  
      sort(x, x + N + 2);  
      int ans;  
      int lb = 0, ub = L;  
      while (lb <= ub) {  
           int mid = (lb + ub) / 2;  
           if (C(mid)) {  
                ans = mid;  
                lb = mid + 1;  
           }  
           else ub = mid - 1;  
      }  
      printf("%d\n", ans);  
 }  
 int main()  
 {  
      cin >> L >> N >> M;  
      for (int i = 1; i <= N; i++) cin >> x[i];  
      x[N + 1] = L;  
      solve();  
      return 0;  
 }