PKU 3258 River Hopscotch

• 直接解をを求めようとすると難しいです
• ある値が与えられたとき、その値が解として正しいかどうかは線形時間で求めることができます
• コレを使って解を二分探索で求めることができます

int pickupGreedy(const vector<int>& ds, int length)
{
	int result = 0;
	int lastPosition = 0;
	for (vector<int>::const_iterator it = ds.begin(); it != ds.end(); ++it) {
		if (*it - lastPosition >= length) {
			++result;
			lastPosition = *it;
		}
	}

	return result;
}

int main()
{
	int L, N, M;
	cin >> L >> N >> M;
	vector<int> ds;
	ds.push_back(L);
	for (int i = 0; i < N; ++i) {
		int d;
		cin >> d;
		ds.push_back(d);
	}

	sort(ds.begin(), ds.end());

	int left = 0;
	int right = 1 << 30;
	while (left + 1 < right){
		ll middle = (left + right) / 2;
		if (pickupGreedy(ds, middle) >= N - M + 1){
			left = middle;
		} else {
			right = middle;
		}
	}

	cout << left << endl;
}