POJ2456 Agressive Cows

Code

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define N 100001
using namespace std;
int x[N],n,m;
bool Judge(int d){
	int last = 1;
	for(int i = 2;i <= m;++i){
		int crt = last + 1;
		while(crt <= n && x[crt] - x[last] < d) ++crt;
		if(crt == n + 1) return 0;
		last = crt;
	}
	return 1;
}
void solve(){
	sort(x + 1,x + n + 1);
	int lb = 0,ub = 1000000001;
	while(lb + 1 < ub){ //边界？
		int mid = (lb + ub)/2;
		if(Judge(mid)) lb = mid;
		else ub = mid;
	}
	printf("%d",lb);
}
int main(){
	scanf("%d %d",&n,&m);
	for(int i = 1;i <= n;++i){
		scanf("%d",&x[i]);
	}
	solve();	
	return 0;
}

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define N 100001
using namespace std;
int x[N],n,m;
bool Judge(int d){
	int last = 1;
	for(int i = 2;i <= m;++i){
		int crt = last + 1;
		while(crt <= n && x[crt] - x[last] < d) ++crt;
		if(crt == n + 1) return 0;
		last = crt;
	}
	return 1;
}
void solve(){
	sort(x + 1,x + n + 1);
	int lb = 0,ub = 1000000001;
	while(lb <= ub){
		int mid = (lb + ub)/2;
		if(Judge(mid)) lb = mid + 1; // ans = mid
		else ub = mid - 1;
	}
	printf("%d",lb - 1);//printf("%d",&ans);
}
int main(){
	scanf("%d %d",&n,&m);
	for(int i = 1;i <= n;++i){
		scanf("%d",&x[i]);
	}
	solve();		
	return 0;
}

https://www.luogu.org/blog/tarjanfloydDP/qian-tan-er-fen-di-bian-jie-wen-ti#