2456:Aggressive cows（二分查找）

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int N,C;
 4 int a[100000];
 5 int fun(int d) {
 6     int temp=a[0], k=1;
 7     for(int i=1; i<N; i++) {
 8         if(a[i]-temp>=d) {
 9             temp=a[i];
10             k++;
11         }
12     }
13     if(k>=C)return 1;
14     else return -1;
15 }
16 int main() {
17     while(cin>>N>>C) {
18         int ans=0;
19         for(int i=0; i<N; i++) {
20             cin>>a[i];
21         }
22         sort(a,a+N);
23         int left=1,right=a[N-1]-a[0];
24         while(left<=right){
25             int mid=left+(right-left)/2;
26             if(fun(mid)>0){
27                 left=mid+1;
28             }
29             else right=mid-1;
30         }
31         cout<<left-1<<endl;
32     }
33     return 0;
34 }