POJ 2456 Aggressive cows

二分答案+贪心

#include <iostream>
#include <algorithm>

using namespace std;

const int MAXN=100111;
const int INF=1034567890;

int N, M;
int Num[MAXN];
int Left, Right, Mid;

bool Test(int k){
	int l=M;
	for(int i=1, p=-k;i<=N;++i){
		if(Num[i]-p>=k){
			--l;p=Num[i];
		}
	}
	return l<=0;
}

int main(){
	ios_base::sync_with_stdio(false);
	
	while(cin >> N >> M){
		for(int i=1;i<=N;++i){
			cin >> Num[i];
		}
		sort(Num+1, Num+N+1);
		Left=0;Right=INF;
		while(Left<Right){
			Mid=(Left+Right)>>1;
			if(Test(Mid+1))	Left=Mid+1;
			else	Right=Mid;
		}
		Mid=(Left+Right)>>1;
		cout << Mid << endl;
	}
	
	return 0;
}