NYOJ 586 瘋牛

瘋牛

描述

農夫 John 建造了一座很長的畜欄，它包括N (2 <= N <= 100,000)個隔間，這些小隔間依次編號為x1,...,xN (0 <= xi <= 1,000,000,000).
但是，John的C (2 <= C <= N)頭牛們並不喜歡這種布局，而且幾頭牛放在一個隔間裡，他們就要發生爭斗。為了不讓牛互相傷害。John決定自己給牛分配隔間，使任意兩頭牛之間的最小距離盡可能的大，那麼，這個最大的最小距離是什麼呢？

輸入

有多組測試數據，以EOF結束。
第一行：空格分隔的兩個整數N和C
第二行——第N+1行：分別指出了xi的位置

輸出

每組測試數據輸出一個整數，滿足題意的最大的最小值，注意換行。

樣例輸入

5 3
1
2
8
4
9

樣例輸出

3

二分+貪心！

AC碼：

#include
#include
#include
using namespace std;
int num[100005],n,c;
int judge(int x)
{
	int cnt=1,temp=num[0],i;
	for(i=1;i=x)
		{
			cnt++;      // 牛的頭數加1
			temp=num[i];
			if(cnt>=c)  // 如果在平均最短長度為x時，c頭都能放的下
				return 1;
		}
	}
	return 0;
}
int get_ans()
{
	int l=0,r=num[n-1]-num[0],mid;
	while(l<=r)
	{
		mid=(l+r)/2;
		if(judge(mid))
			l=mid+1;
		else
			r=mid-1;
	}
	return l-1;
}
int main()
{
	int i;
	while(~scanf("%d%d",&n,&c))
	{
		for(i=0;i