2456 Aggressive cows

 1 #include <stdio.h>
 2 #include <iostream>
 3 #include <cstring>
 4 #include <vector>
 5 #include <algorithm>
 6 const int si = 100010, inf = 1000000000 + 10;
 7 using namespace std;
 8 int N, COW;
 9 int ar[si];
10 
11 bool c(int dis) {
12     int pre = 0, finished = 1;
13     //if (ar[N - 1] - ar[0] < dis) return false;//剪枝 一个都放不下
14     for (int i = 1; i < N && finished < COW; i++) {
15         //if (ar[N - 1] - ar[pre] < dis && COW - finished >= 1) return false;//剪枝 一个都放不下
16         if (ar[i] - ar[pre] >= dis) {
17             finished++;
18             pre = i;
19         }
20     }
21     return finished >= COW;
22 }
23 int main() {
24     cin >> N >> COW;
25     for (int i = 0; i < N; i++) scanf("%d", &ar[i]);;
26     sort(ar, ar + N);
27     int l = 1, m, r = inf;
28     while (l < r - 1) {
29         m = l + r >> 1;
30         if (c(m)) l = m;
31         else r = m;
32     }
33     cout << l << endl;
34     return 0;
35 }