1433: [example 1] angry cattle

• One pass portal
• Typical examples of dichotomy , Find the minimum and the maximum , Just use two points
• Two points + The judgment is feasible

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+3;
int n,m,x[N];
bool check(int d){
    // To see if it works 
	int cow=1,rgt=x[1]+d;
	for(int i=2;i<=n;i++){
    
		if(x[i]<rgt) continue;// The distance is small , next 
		++cow;// feasible , Number of cattle plus one 
		rgt=x[i]+d;// Next position 
	}
	return cow>=m;// Return value 
}
int main()
{
    
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		cin>>x[i];
	sort(x+1,x+n+1);// The cowshed position input is out of order , Need to sort 
	int l=0,r=x[n]-x[1];
	while(l<=r){
    
		int mid=(l+r)>>1;
		if(check(mid)) l=mid+1;// Two points to the right 
		else r=mid-1;// Two points to the left 
	}
	cout<<r<<endl; 
	return 0;
}