[USACO05FEB] 进击的奶牛 Aggressive Cows G

题意

有 n 间牛舍，每间牛舍在一条直线上的某个坐标位置。要从中选择 m 间牛舍放牛，每间牛舍最多放一头牛。

希望任意两头牛之间的最小距离尽可能大，输出这个最大值。

思路

先看一个可以直接验证想法的朴素解：

cpp

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#include <bits/stdc++.h>
using namespace std;

int n, m;
int x[105];

bool canPut(int dist) {
    int cnt = 1;
    int last = x[1];
    for (int i = 2; i <= n; i++) {
        if (x[i] - last >= dist) {
            cnt++;
            last = x[i];
            if (cnt >= m) return true;
        }
    }
    return cnt >= m;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> x[i];
    sort(x + 1, x + n + 1);

    int ans = 0;
    for (int dist = 0; dist <= x[n] - x[1]; dist++) {
        if (canPut(dist)) ans = dist;
    }

    cout << ans << '\n';
    return 0;
}

下面是另一种「01 序列」风格的暴力写法。它按牛舍位置依次决定放牛或不放，递归生成完整选择后，叶子节点统一检查牛的数量和两两距离，并统计最优答案：

另一种暴力写法：01 序列

cpp

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64// brute_01_style.cpp：01 序列风格暴力，按牛舍位置依次决定放牛或不放。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 35;

int n, m;
int x[MAXN];
int choose_cow[MAXN]; // choose_cow[i] = 0/1，表示第 i 个牛舍不放/放牛
int answer;

bool check() {
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        if (choose_cow[i] == 1) cnt++;
    }
    return cnt == m;
}

int calc_answer() {
    int last_pos = -1;
    int min_dist = 1000000000;
    for (int i = 1; i <= n; i++) {
        if (choose_cow[i] == 0) continue;
        if (last_pos != -1) {
            min_dist = min(min_dist, x[i] - last_pos);
        }
        last_pos = x[i];
    }
    return min_dist;
}

void dfs_choose(int dep) {
    if (dep == n + 1) {
        if (check()) {
            int value = calc_answer();
            if (answer < value) answer = value;
        }
        return;
    }

    // 第 dep 个牛舍的 01 选择：0 不放，1 放。
    for (int i = 0; i <= 1; i++) {
        choose_cow[dep] = i;
        dfs_choose(dep + 1);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> x[i];
    }
    sort(x + 1, x + n + 1);

    answer = 0;
    dfs_choose(1);

    cout << answer << '\n';
    return 0;
}

如果直接枚举放牛方案，组合数量太大。brute.cpp 退一步枚举可能的距离，然后用贪心检查，但距离范围可以到 $10^9$ ，正式解法还需要继续优化。

这题是 rbook《二分查找》文章中提到的“最大化最小距离”模型：

直接求最优值很难，但给定一个距离 d，可以检查是否可行。

对固定距离 d，检查方法是贪心：

先排序牛舍坐标。
第一头牛放在最左边的牛舍。
之后从左到右扫描，只要当前牛舍距离上一头牛至少 d，就放一头牛。
如果最终能放下 m 头牛，说明距离 d 可行。

为什么这个贪心正确？因为每次都尽量靠左放牛，会给后面的牛留下最多空间。如果这样都放不下，改成更靠右的位置只会让后续空间更少。

样例中的可行性

样例排序后的牛舍坐标是：

text

11 2 4 8 9

这张表展示几个距离的检查结果。

距离 `d`	一种贪心放法	能否放下 3 头
`2`	`1,4,8`	能
`3`	`1,4,8`	能
`4`	`1,8`	不能

所以最大可行距离是 3。

可行性具有单调性：如果距离 d 可行，那么所有更小的距离也可行。因此可以二分最大可行距离。

代码

cpp

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#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100000 + 5;
int n, m;
int x[MAXN];

bool canPut(int dist) {
    int cnt = 1;
    int last = x[1];
    for (int i = 2; i <= n; i++) {
        if (x[i] - last >= dist) {
            cnt++;
            last = x[i];
            if (cnt >= m) return true;
        }
    }
    return cnt >= m;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> x[i];

    sort(x + 1, x + n + 1);

    int l = 0, r = x[n] - x[1];
    while (l < r) {
        int mid = (l + r + 1) / 2;
        if (canPut(mid)) {
            l = mid;
        } else {
            r = mid - 1;
        }
    }

    cout << l << '\n';
    return 0;
}

复杂度

排序牛舍坐标需要 $O(n log n)$ 。
二分距离约 $O(log 10^9)$ 次，每次检查 $O(n)$ 。
总时间复杂度 $O(n log n + n log 10^9)$ 。
空间复杂度 $O(n)$ 。

总结

这题的关键词是“最大化最小值”。遇到这类题时，可以先问自己：如果给定一个答案，我能不能快速判断它是否可行？

本题中“最小距离至少为 d 是否可行”可以用贪心检查，并且可行性随 d 增大单调变化，所以二分答案正好适用。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。