题目描述：
农夫约翰建造了一座有n间牛舍的小屋，牛舍排在一条直线上，第i间牛舍在x
i
的位置，但是约翰的m头牛对小屋很不满意，因此经常互相攻击。约翰为了防止牛之间互相伤害，因此决定把每头牛都放在离其它牛尽可能远的牛舍。也就是要最大化最近的两头牛之间的距离。
牛们并不喜欢这种布局，而且几头牛放在一个隔间里，它们就要发生争斗。为了不让牛互相伤害。John 决定自己给牛分配隔间，使任意两头牛之间的最小距离尽可能的大，那么，这个最大的最小距离是多少呢？
输入样例:
5 3 1 2 8 4 9
输出样例:
3
解题思路及代码：
采用二分法处理
Java代码：（12分，超时了）
import java.util.Arrays; import java.util.Scanner; //对于n个牛舍，有m个牛，需要求牛舍间的最大距离，也就是不断尝试不同的分法，使用二分法就会很快 public class Main { static int home[] = new int[100005]; static int n,m; public static void main(String[] args) { // TODO Auto-generated method stub Scanner scanner = new Scanner(System.in); n = scanner.nextInt(); m = scanner.nextInt(); int ans=0; for(int i=1;i<=n;i++) { home[i]=scanner.nextInt(); } Arrays.sort(home,1,n+1);//java自带的对数组的升序，经过调优的快速排序法，还可以对部分排序，加入相应的下标参数 int left = 1,right = home[n]-home[1];//left是二分查找的最小值，right是最大值 while(left<=right) {//满足此条件一直查找 int mid = (left+right)/2; if(check(mid)) { left = mid+1; ans=mid; }else { right = mid-1; } } System.out.print(ans); } public static boolean check(int d) {//d为牛舍的间隔 int next = home[1]+d;//下一个牛舍的位置,初始化为第二个 int cow = 1;//第一个位置肯定有牛 for(int i=2;i<=n;i++) { if(home[i]>=next) { cow++; next = home[i]+d; } } if(cow>=m) return true; else return false; } }
c++代码：
#include<iostream> #include<algorithm> using namespace std; const int N=1e5+3; int n,m,x[N]; inline bool check(int d){ //以d为答案，看是否正确 int cow=1; int rgt=x[1]+d; for(int i=2;i<=n;i++){ if(x[i]<rgt) continue; //不符合跳过 ++cow; rgt=x[i]+d; //符合计数并更新rgt } return cow>=m; //cow>=m是成立 } int main(){ cin>>n>>m; for(int i=1;i<=n;i++) cin>>x[i]; sort(x+1,x+1+n); //二分查找 int l=0,r=x[n]-x[1]; while(l<=r){ int mid=l+r>>1; if(check(mid)) l=mid+1; else r=mid-1; } cout<<r<<endl; return 0; }
