信息学奥赛一本通T1433-愤怒的牛

题目链接

农夫 John 建造了一座很长的畜栏，它包括N(2≤N≤100,000)个隔间，这些小隔间依次编号为x1,…,xN(0≤xi≤1,000,000,000). 但是，John的C(2≤C≤N)头牛们并不喜欢这种布局，而且几头牛放在一个隔间里，他们就要发生争斗。为了不让牛互相伤害。John决定自己给牛分配隔间，使任意两头牛之间的最小距离尽可能的大，那么，这个最大的最小距离是什么呢
输入
第一行：空格分隔的两个整数N和C；

第二行—第N+1行：i+1行指出了xi的位置。

输出
一个整数，最大的最小值。
样例输入

5 3
1 2 8 4 9

样例输出

提示

把牛放在1，4，8这样最小距离是3。

二分 + 贪心
对于二分，我们的二分对象是什么呢？
那么我们就要理解题目了，题目的意思就是给定了一些间隔，同时我们也可以将这些间隔看做是一个点，然后将 c 头牛放到一些点上面，保证最优解的情况是每头牛之间的间隔是最大的，同时我们要求出最优解的情况下的间隔最小值
显然，经过这样分析后，我们可以明确二分的对象就是间隔的最小值，所以我们在二分答案时候的判断条件就是，二分的答案是否满足任意两头牛之间的间隔大于等于我们的二分答案
那么现在就又出现了一个问题就是，我们是如果满足二分答案的同时还是最优解呢？
因此我们就需要对原数据进行一次从小到大的排序，那么是为什么呢？…其实我也不知道，反正题目给的提示是进行排序，管他呢，sort 大法好！！！

上代码

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<stack>
#include<queue>
#include<sstream>

using namespace std;
typedef long long ll;
const int N = 100010;
const int MOD = 100000007;

int n, c;
int p[N];

int check(int mid)
{
	int count = 1;
	int t = p[0];
	for(int i = 1; i < n; i ++ )
	{
		if(p[i] - t >= mid)
		{
			count ++ ;
			t = p[i];
			if(count >= c) return 1;
		}
	}
	return 0;
}

int main()
{
	cin >> n >> c;
	for(int i = 0; i < n; i ++ ) cin >> p[i];
	sort(p, p + n);
	int l = 0, r = p[n - 1] - p[0], mid;
	while(l <= r)
	{
		mid = (l + r) / 2;
		if(check(mid)) l = mid + 1;
		else r = mid - 1;
	}
	cout << r << endl;
	return 0;
}