-
Notifications
You must be signed in to change notification settings - Fork 11
/
SPOJ297.cc
49 lines (45 loc) · 1.11 KB
/
SPOJ297.cc
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
// SPOJ 297: Aggressive Cows
// http://www.spoj.com/problems/AGGRCOW/
//
// Solution: binary search
//
// Let f(d) = true if there is >= d placement,
// false otherwise.
// Then f is monotone decreasing with respect to d, and
// the solution is the maximum d with f(d) == true.
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <functional>
#include <algorithm>
using namespace std;
#define fst first
#define snd second
#define all(c) c.begin(), c.end()
int f(const vector<int> &a, int d) {
int c = 1, j = 0;
for (int i = 1; i < a.size(); ++i)
if (a[i] - a[j] >= d) { j = i; ++c; }
return c;
}
int main() {
int ncase;
scanf("%d", &ncase);
for (int icase = 0; icase < ncase; ++icase) {
int n, m;
scanf("%d %d", &n, &m);
vector<int> a(n);
for (int i = 0; i < n; ++i)
scanf("%d", &a[i]);
sort(all(a));
int lo = 1, hi = a.back()+1;
while (hi - lo >= 2) { // f(lo) >= m, and f(hi) < m
int mid = (lo + hi) / 2;
int s = f(a, mid);
if (s >= m) lo = mid; else hi = mid;
}
printf("%d\n", lo);
}
}