POJ 2456 疯牛(二分+贪心)

题目链接，请点击！

思路：
这道题的话，其实就是贪心+二分，总的一句话，就是把距离二分后的x,然后拿x去遍历数组，看是否满足c个以上的牛，若满足，就true
在此之前要先把牛栏的编号先排个序，为什么排序呢？排序的目的是为了验证二分后的距离是否满足c个牛的这个条件，如果满足这个距离是OK的

# include <iostream>
# include <algorithm>
using namespace std;
int n,c;
const int N = 1e5+10;
int a[N];

bool check(int st){
	int pre = a[0];
	int sum = 1;
	for(int i=1;i<n;++i){
		if(a[i]-pre >= st){
			++sum;
			pre = a[i];
			if(sum>=c) return true;
		}
	}
	return false;
}
int main(void)
{
	cin>>n>>c;
	for(int i=0;i<n;++i){
		cin>>a[i];
	} 
	
	sort(a,a+n);
	
	int l = 0,r = a[n-1] - a[0];
	int ans = 0;
	
	while(l<r){
		int mid = (l+r +1 ) >> 1 ;
		if(check(mid)){
			l = mid;
		}else{
			r = mid-1;
		}
	}
	cout<<l<<endl;
	return 0;
 } 

---

---

跟力扣的1552. 两球之间的磁力是一样的意思