poj 2456 Aggressive cows（二分）

Farmer John has built a new long barn, with N (2 <= N <= 100,000) stalls. The stalls are located along a straight line at positions x1,...,xN (0 <= xi <= 1,000,000,000).

His C (2 <= C <= N) cows don't like this barn layout and become aggressive towards each other once put into a stall. To prevent the cows from hurting each other, FJ want to assign the cows to the stalls, such that the minimum distance between any two of them is as large as possible. What is the largest minimum distance?

Input

* Line 1: Two space-separated integers: N and C

* Lines 2..N+1: Line i+1 contains an integer stall location, xi

Output

* Line 1: One integer: the largest minimum distance

Sample Input

5 3
1
2
8
4
9

Sample Output

3

Hint

OUTPUT DETAILS:

FJ can put his 3 cows in the stalls at positions 1, 4 and 8, resulting in a minimum distance of 3.

Huge input data,scanf is recommended. 

看了题解才弄懂怎么做...漫漫进阶路...小白仍需努力啊...

（参考了 http://blog.csdn.net/qq_34374664/article/details/53366987）

一点小小的启发（吧...）

1.二分的灵活性 （其实看懂题目之后我都没想出来怎么用二分

2.最小值的最大化 最大值的最小化（看到英文的时候其实有点蒙...)

3.一点小小的问题 就是最后为什么输出的是mid呢...其实还没有想通

思路什么的其实都在注释上面了 就懒得再写一次了

#include<iostream>
#include<cstdio>
#include <cstring> 
#include<algorithm>
using namespace std;
const int MAXN = 1e5 + 5,inf=1e9+5;
int n, c, num[MAXN];
bool judge(int dis)//判断最小距离为dis的情况下能不能把c头牛都安顿好
{
	int last = 0;//第1头牛安顿在0的位置
	int cur = last + 1;//看看能不能把下一头牛安顿在last的下一个棚
	for (int i = 1; i < c; i++)
	{
		while (cur < n && num[cur] - num[last] < dis)
			cur++;//移动呀移动~~
		
		if (cur == n)return false;//还没安排好所有的牛呢 就到末尾了
		last = cur;
	}
	return true;
}
int main()
{
	while (~scanf_s("%d%d", &n, &c))
	{
		for (int i = 0; i < n; i++)
			scanf_s("%d", &num[i]);//每个棚子的距离
		sort(num, num + n);
		//二分找最大的min值
		int min = 0, max = num[n-1] ;
		int mid = (min + max) / 2;
		while (max - min > 1)
		{
			mid = (min + max) / 2;
			if (judge(mid) == true)min = mid;
			else max = mid;
		}
		cout << min << endl;//这里为什么是输出min 还是不太明白
	}
}