机场大巴(二分查找与二分答案)

题目描述

一场神秘大会要在小明的家里举办了！

他的处于世界各地的客人将会到达当地的机场，前来参会。具体地说，有 N个客人到达了机场（1≤N≤100000），其中客人 i在时间 ti（0≤ti≤10^9）到达。小明安排了 M（1≤M≤10^5 ）辆大巴来机场接这些客人。每辆大巴可以乘坐 C个客人（1≤C≤N）。小明正在机场等待客人们到来，并且准备安排到达的客人们乘坐大巴。当最后一个乘坐某辆大巴的客人到达的时候，这辆大巴就可以发车了。小明想要做一个优秀的主办者，所以并不想让客人们在机场等待过长的时间。如果小明合理地协调这些大巴，等待时间最长的客人等待的时间的最小值是多少？一个客人的等待时间等于他的到达时间与他乘坐的大巴的发车时间之差。

输入数据保证M×C≥N。

输入格式

输入的第一行包含三个空格分隔的整数 N，M，和 C。第二行包含N个空格分隔的整数，表示每个客人到达的时间。

输出格式

输出一行，包含所有到达的客人中的最大等待时间的最小值。

输入样例

6 3 2
1 1 10 14 4 3

输出样例

4

说明/提示

如果两个时间 1到达的客人乘坐一辆巴士，时间 3和时间 4到达的客人乘坐乘坐第二辆，时间 10和时间 14到达的客人乘坐第三辆，那么等待时间最长的客人等待了 4个单位时间（时间 10到达的客人从时间 10等到了时间 14）。

#include<bits/stdc++.h>
using namespace std;

int a[1000100], N, M, C, l, r, mid, res;

int f(int x) {
	int s = 1; 
	int now = 1; 
	int ss = 1; 
	for (int i=2;i<=N;i++) {
		if (a[i] - a[now] <= x && ss < C) {
			ss ++; 
		} 
		else {
			s ++;
			now = i;
			ss = 1; 
		} 
	} 
	if (s <= M) return 1;
	else return 0; 
} 

int main() {
	scanf("%d%d%d", &N, &M, &C);
	for (int i = 1; i <= N; i++) scanf("%d", &a[i]);
	sort(1 + a, 1 + a + N);
	l = 1;
	r = a[N] - a[1];
	while (1) {
		if (l == r) {
			printf("%d\n", l);
			break;
		}
		mid = (l + r) / 2;
		res = f(mid);
		if (res == 1)  r = mid;
		else l = mid + 1;
	}

}