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?

5 312849Sample Output
3HintOUTPUT 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思路：二分法+貪心如果不適用貪心，很容易時(shí)間超限。貪心思路：最小間隔0與最大間隔（str[N]-str[0]）/(C-1),距離不斷縮小,直到區(qū)間為0。
#include<cstdio>#include<algorithm>#include<cstdlib>using namespace std;int N,C;int str[1000005];int greed(int n){   int imax=str[1],sum=0;    for(int i=1;i<=N;i++)    {        if(str[i]-imax>=n)        {            sum++;          imax=str[i];        }    }      return sum>=C-1? 1:0;//判斷}int main(){    //freopen("e;//in.txt","r",stdin);   while(scanf("%d%d",&N,&C)==2)   {       for(int i=1;i<=N;i++)        scanf("%d",&str[i]);        sort(str,str+N);       //輸入       int left=0,right=(str[N]-str[0])/(C-1),mid;       while(left<=right)       {           mid=(left+right)/2;           if(greed(mid))//如果間隔為mid，可以放下            left=mid+1;           else //不可以放下            right=mid-1;       }       printf("%d/n",left-1);//特別注意mid 有可能不能放下c 只羊，我們能夠確定left 左邊的能夠放下c 只羊，right 右邊的不能放下c 只羊，可是mid 不能確定；如果mid 能夠放下，則left 右移，left=right+1 ，顯然不能放下，則left-1 是最大值；如果mid 不能放下，則left 不變，left 依然不能不能放下，left-1 是最大值   }   return 0;}