Peking University Online Judge 3258 River Hopscotch

なぜか最近POJとの相性が良くなってきたので、ACコードを貼っていきます。
この問題は二分探索で通しました。

#include<iostream>
#include<algorithm>
using namespace std;
static const int MAX_N = 100000;
static const int MAX_D = 1000000000;

int L, N, M;
int D[MAX_N + 2];

int main(){
	cin >> L >> N >> M;
	for(int i = 1; i < N + 1; i++) cin >> D[i];
	D[0] = 0, D[N + 1] = L;
	sort(D, D + N + 2);
	
	int lb = 0, ub = MAX_D + 1;
	while(ub - lb > 1){
		int mid = lb + (ub - lb) / 2;
		int cnt = 1;
		for(int i = 0; i < N + 2; i++){
			int dist = mid;
			while(dist >= D[i + 1] - D[i] && i < N + 2){
				dist -= D[i + 1] - D[i];
				i++;
			}
			cnt++;
		}
		if(N + 2 - cnt >= M) ub = mid;
		else lb = mid;
	}
	
	cout << ub << endl;
	return 0;
}