愤怒的牛

农夫 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

3

这一类题目属于最小值最大化(最大值最小化)，这类题目一般用二分法求解。

在这里我们需要一个judge函数，judge函数的功能：是否有c头牛之间的距离不小于mid，如果有，就证明mid是有效的。

#include<iostream> #include<algorithm> const int size = 100005; using namespace std; int n,c,ans; int arr[size]; bool judge(int x){ int cnt = 1, last = 1; for(int i = 2; i <= n; i ++){ if(arr[i] - arr[last] >= x){ cnt++; last = i; } if(cnt >= c){ return true; } } return false; } int main(){ cin >> n >> c; for(int i = 1; i <= n; i ++){ cin >> arr[i]; } sort(arr+1,arr+n+1); int left = arr[1], right = arr[n] - arr[1]; while(left <= right){ int mid = (left+right)>>1; if(judge(mid)){ left = mid + 1; ans = mid; }else{ right = mid - 1; } } cout << ans << endl; }