2018-2-6
直接使用二分搜索即可，如果可以满足条件的话，就在mid与high之间，否则的话就在low与mid之间。
在判断给定的d是否能够满足条件时，我用的是贪心的想法，就是让牛尽可能的朝左边的牛棚中去，这样很容易就可以判断出来。
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;const int N = 100000;
int x[N+1];
int n,c,cnt;bool res(int d){cnt=1;int e=x[1];for (int i=2;i<=n;i++){if (x[i]-e>=d){cnt++;e=x[i];}}return cnt>=c;
}void div(){int l=0,h=x[n]-x[1];while (h-l>1){int m=(l+h)/2;if (res(m)) l=m;else h=m;}cout<<l<<endl;
}int main(){while (cin>>n>>c){for (int i=1;i<=n;i++){scanf ("%d",x+i);}sort(x+1,x+n+1);div();}return 0;
}其实我一直有一个疑问，就是在二分搜索中，high什么时候等于mid，什么时候等于mid-1，low什么时候等于mid，什么时候等于mid+1，返回的值什么时候等于mid，什么时候等于high，什么时候等于low……