洛谷p1138-进击的奶牛

题目描述

算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<bits/stdc++.h>


using namespace std;
const int N=1e5;
int niu[N];
int n;
int m;
bool check(int mid)  
{
   int  t=1  ; // 初始一定要用一个牛棚
    int first=niu[0]; 
   for(int i=1;i<n;i++)
           {   if((niu[i]-first)>=mid)  {first=niu[i];  t++;}//如果当前相邻的距离大于二分的值 说明这个值符合要求   更新first 牛棚加一  比较下一个
               else     continue;
                
           }
 
   return t>=m;

}



//所有牛中相邻两头的最近距离越大越好。那么，这个最大的最近距离是多少呢？  意思是选出一个最佳距离x  使得每个相邻的距离都比这个距离大  而且这个x是要最大的 意思为最小最大值
int main() 
{     cin>>n>>m;
      for(int i=0;i<n;i++) 
         {  
             cin>>niu[i];  
               

         }   //数据乱序 需要排序
     sort(niu,niu+n);
    int l=0;
    int r=1e9;
    while(l<r)
      {   int mid=l+r+1>>1;
          if(!check(mid)) l =mid;
          else   r=mid-1;
     

      }

     cout<<r; 


     return 0;
}

图解