1 /* 2     二分搜索：搜索安排最近牛的距离不小于d  3 */ 4 #include 
     
       5 #include 
      
        6 #include 
       
         7 using namespace std; 8  9 const int MAXN = 1e5 + 10;10 const int INF = 0x3f3f3f3f;11 int x[MAXN];12 int n, m;13 14 bool check(int d)   {15     int last = 1;16     for (int i=1; i<=m-1; ++i)    {17         int cur = last + 1;18         while (cur <= n && x[cur] - x[last] < d)    cur++;19         if (cur == n + 1)   return false;20         last = cur;21     }22     return true;23 }24 25 int main(void)  {       //POJ 2456 Aggressive cows 26     //freopen ("POJ_2456.in", "r", stdin);27 28     while (scanf ("%d%d", &n, &m) == 2)   {29         for (int i=1; i<=n; ++i)    {30             scanf ("%d", &x[i]);31         }32 33         sort (x+1, x+1+n);34         int l = 0, r = INF;35         while (l + 1 < r)   {36             int mid = (l + r) >> 1;37             if (check (mid))    l = mid;38             else    r = mid;39         }40         printf ("%d\n", l);41     }42 43     return 0;44 }