Social Distancing I

题意

有一排牛栏，1 表示已有奶牛，0 表示空栏。

现在要把两头新奶牛放进两个空栏中。设最终所有相邻奶牛之间的最小距离为 D，求 D 的最大值。

思路

暴力想法

小数据可以直接枚举两头新牛分别放在哪两个空栏，然后扫描最终字符串，计算相邻 1 的最小距离：

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
65/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-11 14:04
 * update_at: 2026-07-11 14:06
 */
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 30;

int n;
string s;

int calc_min_distance(const string &str) {
    int last = -1;
    int best = 1000000000;

    for (int i = 0; i < n; i++) {
        if (str[i] == '1') {
            if (last != -1 && i - last < best) {
                best = i - last;
            }
            last = i;
        }
    }

    return best;
}

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

    cin >> n >> s;

    int ans = 0;

    // 枚举两头新牛分别放在哪两个空栏。
    for (int i = 0; i < n; i++) {
        if (s[i] != '0') {
            continue;
        }
        for (int j = i + 1; j < n; j++) {
            if (s[j] != '0') {
                continue;
            }

            string t = s;
            t[i] = '1';
            t[j] = '1';

            int value = calc_min_distance(t);
            if (ans < value) {
                ans = value;
            }
        }
    }

    cout << ans << '\n';

    return 0;
}

这个暴力枚举了完整放置方案，逻辑最直接。但空栏最多有 $N$ 个，枚举两个位置再扫描字符串，复杂度是 $O(N^3)$ ，不能应对 $N \leqslant 10^5$ 。

候选位置

把连续的 0 看成空段。

如果只在一个内部空段放一头牛，最优位置应该尽量靠中间；如果放在边缘空段，最优位置就是整个序列的最左端或最右端。

如果两头新牛放进同一个内部空段，为了让“左边已有牛到第一头新牛、两头新牛之间、第二头新牛到右边已有牛”这三段的最小值尽量大，它们应该放在三等分附近。

因此只需要尝试这些候选：

两头都放进同一个最大内部空段的三等分点。
两头分别放在最左端和最右端。
一头放最左端，另一头放当前最大内部空段中心。
一头放最右端，另一头放当前最大内部空段中心。
先在最大内部空段中心放一头，再继续放新的最大内部空段中心。

每次构造一个候选字符串后，扫描相邻 1 的距离，就能得到这个方案的 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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-11 14:04
 * update_at: 2026-07-11 14:06
 */
#include <bits/stdc++.h>
using namespace std;

int n;
string s;

// 找两个已有奶牛之间最大的内部空段，返回两头奶牛的距离。
int find_largest_gap(const string &str, int &gap_start) {
    int biggest_gap = 0;
    int current_start = -1;

    for (int i = 0; i < n; i++) {
        if (str[i] == '1') {
            if (current_start != -1 && i - current_start > biggest_gap) {
                biggest_gap = i - current_start;
                gap_start = current_start;
            }
            current_start = i;
        }
    }

    return biggest_gap;
}

// 计算当前方案里最近两头奶牛的距离。
int find_smallest_gap(const string &str) {
    int smallest_gap = 1000000000;
    int last = -1;

    for (int i = 0; i < n; i++) {
        if (str[i] == '1') {
            if (last != -1 && i - last < smallest_gap) {
                smallest_gap = i - last;
            }
            last = i;
        }
    }

    return smallest_gap;
}

// 在当前最大内部空段中心放一头牛，然后返回最小距离。
int try_cow_in_largest_gap(string str) {
    int gap_start = -1;
    int largest_gap = find_largest_gap(str, gap_start);

    if (largest_gap >= 2) {
        str[gap_start + largest_gap / 2] = '1';
        return find_smallest_gap(str);
    }

    return -1;
}

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

    cin >> n >> s;

    int answer = 0;
    string t;

    // 情况 1：两头新牛都放进同一个最大的内部空段，近似放在三等分点。
    int gap_start = -1;
    int largest_gap = find_largest_gap(s, gap_start);
    if (largest_gap >= 3) {
        t = s;
        t[gap_start + largest_gap / 3] = '1';
        t[gap_start + largest_gap * 2 / 3] = '1';
        answer = max(answer, find_smallest_gap(t));
    }

    // 情况 2：两头新牛分别放在最左端和最右端。
    if (s[0] == '0' && s[n - 1] == '0') {
        t = s;
        t[0] = '1';
        t[n - 1] = '1';
        answer = max(answer, find_smallest_gap(t));
    }

    // 情况 3：一头放最左端，另一头放当前最大内部空段中心。
    if (s[0] == '0') {
        t = s;
        t[0] = '1';
        answer = max(answer, try_cow_in_largest_gap(t));
    }

    // 情况 4：一头放最右端，另一头放当前最大内部空段中心。
    if (s[n - 1] == '0') {
        t = s;
        t[n - 1] = '1';
        answer = max(answer, try_cow_in_largest_gap(t));
    }

    // 情况 5：先在最大内部空段中心放一头，再继续把另一头放到新的最大内部空段中心。
    if (largest_gap >= 2) {
        t = s;
        t[gap_start + largest_gap / 2] = '1';
        answer = max(answer, try_cow_in_largest_gap(t));
    }

    cout << answer << '\n';

    return 0;
}

复杂度

候选方案数量是常数，每个候选方案最多线性扫描字符串，所以时间复杂度为 $O(N)$ 。

需要保存字符串和少量副本，空间复杂度为 $O(N)$ 。

总结

这题容易漏掉“两头新牛放在同一个最大内部空段”的情况。

按照官方解析把候选情况列全，再用统一的扫描函数计算每个方案的最小距离，能把复杂的分类讨论变成比较稳定的模拟代码。

目录

题意

思路

暴力想法

候选位置

代码

复杂度

总结