https://www.luogu.org/problemnew/show/P5119

题意：n头牛，每头牛有一个到达时间，每辆车最多可以接c头牛，总共有m辆车，问怎么安排，使得最大等待时间最小。

思路：最小化最大值，二分。

二分最长的等待时间，这个最大时间越短，越不容易满足条件，越长，越容易满足条件（需要的车辆数<=m），求的是最小的这个最大时间。

check（）函数就是当当前车拉了超过c头牛或者当前牛距离该车开头已超过最大时间时新开辟一辆车。

 

与这道题https://blog.csdn.net/Wen_Yongqi/article/details/86774245不同，那道题求的是总的xxx，最优值未必每一块都有一个固定的xxx，可能一块儿大，一块儿小，总体最优，二分最小的最大值是这样：只要有那个最大值，不管别的怎么小，总体优不优看的是最大值，因此可以二分，而这道题不一样，总体优不优并不是取决于那个最大的，而是看 整体之和，如果强行二分，在该小时大了，就找不到最优了。最后是用贪心做了。

而本题要的是最小的最大值，也就是每一块儿的最大值都小于预设的的最大值，用二分求解。 

也与这道题https://blog.csdn.net/Wen_Yongqi/article/details/87547500不同，那道题没有规定最多可以分多少组，只是规定了每组的最大容量，同样要的是总体最优，每一块儿都不固定怎么怎么样，同样，总体优不优并不取决于那个最大的，而是整体之和，这是不能够二分的。最后用dp做了。

这道题区别于那两题的地方就在于，总体优不优取决于每一段中最大的那个段，这就是二分适用“最小化最大值”的原因。

PS:老感觉https://blog.csdn.net/Wen_Yongqi/article/details/87547500和这道题很像，现在两道题互相融合一下。

①：这道题删掉最多m辆车这个条件，改为不限制车的数量，那就太简单了，直接每头牛派一辆车，最大值就是0。与dp无关。

②：那道题加一个条件：限制最多可以选m个区间，那么dp加一维，设f(i,j):前i个数选了j个区间的最优值，转移时f(i,j)<-max{f(i-x,j-1)+[i-x+1~i]},x∈[1,k]，与二分无关。

由此可见，能不能用二分关键就在于：是不是求最大/小的最小/大值。是这个一般用二分，不是求这个一般不能用二分。

 

#include<bits/stdc++.h>
using namespace std;
#define maxn 100000+1000

int n,m,c,a[maxn],ans;

bool check(int l)
{
	int ret=1,last=1;   //当前正在处理第ret辆车
	for(int i=1;i<=n;i++)
	{
		if(i-last>=c||a[i]-a[last]>l)
		{
			ret++;
			last=i;
		}
	}
	return ret<=m;
}

int main()
{
//	freopen("input.in","r",stdin);
	cin>>n>>m>>c;
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	sort(a+1,a+1+n);
	int l=1,r=a[n]-a[1],mid;
	while(l<=r)
	{
		mid=(l+r)/2;
		if(check(mid))ans=mid,r=mid-1;
		else l=mid+1;
	}
	cout<<ans<<endl;
	return 0;	
}