最大化最小值 Aggressive cows

Aggressive cows　http://poj.org/problem?id=2456

Ｎ间小屋，Ｍ头牛，使得牛跟牛之间的距离最远，以防止牛打架。

２<=N<=100000

2<=M<=N

0 <=x<=10

//////////////////////////////////////////////////////////////

C(d):=可以安排牛的位置使得任意两头牛的间距都不小于ｄ

使用二分搜索法解决：

//参考文献：挑战程序设计大赛（第二版）
/*************************************************************************

    > File Name: AggressiveCows_poj2456.cpp

    > Author: spzhao

    > Mail: [email protected]

    > Created Time: 2015年10月14日 星期三 20时25分30秒

 ************************************************************************/

#include<iostream>

#include <cstdio>

#include <algorithm>

#include <cstring>

#define INF 1000000000

using namespace std;

int N,K;

int x[100005];

bool C(int d)

{

	int last = 0;

	for (int i = 1;i < K;i++)

	{

		int crt = last+1;　　　　　　　　　　　　　　　　　　　　//　只需要比较Ｋ－１次找出最适合的值ｄ来放置Ｋ头牛，用last & crt　来表示上一头牛和当前牛的位置

		while(crt < N && x[crt] - x[last] < d)

			crt++;

		if (crt == N) return false;　　　　　　　　　　　　　// 到达最大值Ｎ说明ｄ的值小了

		last = crt;

	}

	return true;

}

int main ()

{

	cin >> N >> K;

	for (int i = 0;i < N;i++)

		scanf("%d",&x[i]);

	sort(x,x+N);

	int l = 0,r = INF;

	while(r - l > 1)

	{

		int mid = (l+r)/2;

		if (C(mid))

			l = mid;

		else

			r = mid;

	}

	printf("%d\n",l);

	return 0;

}