USACO银组12月月赛题解
Convention
题面
一场别开生面的牛吃草大会就要在Farmer John的农场举办了！
世界各地的奶牛将会到达当地的机场，前来参会并且吃草。具体地说，有N头奶牛到达了机场（1≤N≤105），其中奶牛i在时间ti（0≤ti≤109）到达。Farmer John安排了M（1≤M≤105）辆大巴来机场接这些奶牛。每辆大巴可以乘坐C头奶牛（1≤C≤N）。Farmer John正在机场等待奶牛们到来，并且准备安排到达的奶牛们乘坐大巴。当最后一头乘坐某辆大巴的奶牛到达的时候，这辆大巴就可以发车了。Farmer John想要做一个优秀的主办者，所以并不想让奶牛们在机场等待过长的时间。如果Farmer John合理地协调这些大巴，等待时间最长的奶牛等待的时间的最小值是多少？一头奶牛的等待时间等于她的到达时间与她乘坐的大巴的发车时间之差。
输入保证MC≥N。
输入格式
（文件名：convention.in）：
输入的第一行包含三个空格分隔的整数N，M，和C。第二行包含N
个空格分隔的整数，表示每头奶牛到达的时间。
输出格式
（文件名：convention.out）：
输出一行，包含所有到达的奶牛中的最大等待时间的最小值。
输入样例：
6 3 2
1 1 10 14 4 3
输出样例：
4
如果两头时间1到达的奶牛乘坐一辆巴士，时间2和时间4到达的奶牛乘坐乘坐第二辆，时间10和时间14到达的奶牛乘坐第三辆，那么等待时间最长的奶牛等待了4个单位时间（时间10到达的奶牛从时间10等到了时间14）。
题解
- 看到题面以后以为是摆渡车…
- 不过根据输出格式所说的最大的最小很容易想到二分答案。
题目中求得是等待的时间，因此我们就对等待的时间进行二分答案即可。 - 如何写二分答案的判断函数呢？?
线性扫描区间：
如果当前奶牛之前没有坐车，就坐一辆车，等接下来的车
如果当前奶牛的时间与第一头上车的奶牛时间差在mid以内，且容量够，上车
否则另开一辆车
最后得到所需车的数量 - 判定：车的数量小于m则合法
- 时间复杂度 O ( n l o g n ) O(nlogn)