|
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 |
#include <cstdio>#include <algorithm>using
namespace std;const
int maxl = 100010;int a[maxl];int N, M;inline
bool condition(int
d) { int
pr = 0; for
(int i = 1; i < M; ++i) { //第一次循环可看作是找1 ，2两头牛的距离，第M － 1 次寻找M － 1 和第M头牛之间的距离 int
ne = pr + 1; while
(ne < N && a[ne] - a[pr] < d) ++ne; if
(ne == N) return
false; //要符合当前距离，但是牛舍“不够用了”，距离偏大 pr = ne; } return
true;}int
main(){ while
(scanf("%d%d", &N, &M) != EOF) { int
maxv = 0; for
(int i = 0; i < N; ++i) { scanf("%d", &a[i]); if
(a[i] > maxv) maxv = a[i]; } sort(a, a + N); //二分 int
lp = 0, rp = maxv; while
(rp - lp > 1) { int
mid = (lp + rp) / 2; if
(condition(mid)) lp = mid; else
rp = mid; } printf("%d\n", lp); } return
0;} |
POJ2456 Aggressive cows,布布扣,bubuko.com
原文：http://www.cnblogs.com/WJZDMR/p/3600979.html