POJ2456 Aggressive cows（二分）

 1 #include<iostream>
 2 #include<vector>
 3 #include<cstdio>
 4 #include<algorithm>
 5 #include<cmath>
 6 #include<cstring>
 7 #include<queue>
 8 #include<map>
 9 using namespace std;
10 const int maxn = 1e5+5;
11 typedef long long ll;
12 ll sta[maxn];
13 int N,C; 
14 bool check(ll dis){
15     int sum = 1;
16     int cur = 0;
17     for(int i = 1;i<N;i++){
18         if(sta[i] - sta[cur]>=dis){
19             sum++;
20             cur = i;
21         }
22     }
23     return sum>=C;
24 }
25 int main(){
26     while(cin>>N>>C){
27         for(int i = 0;i<N;i++){
28             cin>>sta[i];
29         }
30         sort(sta,sta+N);
31         ll MAX = -1;
32         for(int i = 1;i<N;i++){
33             MAX = max(MAX,sta[i]-sta[i-1]);
34         }
35         ll l = 0,r = MAX *2;
36         ll mid;
37         while(l<r){
38             mid = (1+l+r)>>1;
39             if(check(mid)){//sum>=C;
40                 l = mid ;
41             }
42             else{
43                 r = mid - 1;
44             }
45         }
46     //    cout<<l<<" "<<r<<endl;
47         cout<<l<<endl;
48     }
49     return 0;
50 }