Social Distancing

题意

数轴上有 $M$ 个互不相交的有草区间，要放置 $N$ 头牛。

所有牛都必须放在整数位置，并且位置上有草。定义 $D$ 为任意两头牛之间的最小距离，要求最大化 $D$ 。

思路

先看一个小数据暴力。它把所有有草的整数位置展开，然后用 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
65
66
67
68
69
70
71
72
73
74/**
 * 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 20:22
 * update_at: 2026-07-11 20:23
 */
// brute.cpp：小数据暴力解，使用 01 序列递归枚举每个可用位置选或不选。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXP = 35;

int n, m;
int tot;
ll pos[MAXP];      // 所有有草的整数位置，仅用于小数据
int choose_pos[MAXP]; // choose_pos[i] 表示第 i 个位置是否放牛
ll ans;

void check_answer() {
    int cnt = 0;
    ll last = -1;
    ll mindist = (ll)4e18;

    for (int i = 1; i <= tot; i++) {
        if (choose_pos[i] == 1) {
            cnt++;
            if (last != -1) {
                mindist = min(mindist, pos[i] - last);
            }
            last = pos[i];
        }
    }

    if (cnt == n) {
        ans = max(ans, mindist);
    }
}

void dfs(int dep) {
    if (dep == tot + 1) {
        check_answer();
        return;
    }

    choose_pos[dep] = 0;
    dfs(dep + 1);

    choose_pos[dep] = 1;
    dfs(dep + 1);
}

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

    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        ll l, r;
        cin >> l >> r;
        for (ll x = l; x <= r && tot + 1 < MAXP; x++) {
            tot++;
            pos[tot] = x;
        }
    }

    sort(pos + 1, pos + tot + 1);
    dfs(1);
    cout << ans << '\n';

    return 0;
}

这个暴力能直接说明问题本质：我们在一堆候选位置里选出 $N$ 个，使得相邻被选位置之间的最小距离最大。

最大化最小值，通常可以二分答案。

假设当前检查的距离是 D，问题变成：

text

1能不能放下 N 头牛，使得任意相邻两头牛距离至少为 D？

判定时用贪心：从左到右扫描区间，每次把下一头牛放在当前能放的最左位置。

这样做不会变差，因为越靠左放，后面剩下的空间只会更多，不会更少。

以样例区间 [0,2] [4,7] [9,9] 检查 $D = 2$ ：

区间	当前最早可放位置	实际放置	放完后最后一头牛
`[0,2]`	0	0, 2	2
`[4,7]`	4	4, 6	6
`[9,9]`	8	9	9

一共能放 5 头，所以 $D = 2$ 可行。

如果某个区间是 [l,r]，上一头牛在 last，那么这个区间内第一头能放的位置是：

pos=\max(last+D,l)

若 $pos <= r$ ，这个区间能放：

\left\lfloor {r-pos \over D} \right\rfloor + 1

头牛。这样一个区间可以一次算完，不需要一头一头循环。

二分时：

如果 D 可行，尝试更大的距离；
如果 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/**
 * 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 20:22
 * update_at: 2026-07-11 20:23
 */
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXM = 100005;

int n, m;
pair<ll, ll> seg[MAXM];

bool check(ll dist) {
    ll cnt = 0;
    ll last = 0;

    for (int i = 1; i <= m; i++) {
        ll pos;
        if (cnt == 0) {
            pos = seg[i].first;
        } else {
            pos = max(last + dist, seg[i].first);
        }

        if (pos <= seg[i].second) {
            ll add = (seg[i].second - pos) / dist + 1;
            cnt += add;
            last = pos + (add - 1) * dist;
            if (cnt >= n) return true;
        }
    }

    return cnt >= n;
}

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

    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        cin >> seg[i].first >> seg[i].second;
    }

    sort(seg + 1, seg + m + 1);

    ll left = 1;
    ll right = seg[m].second - seg[1].first;
    ll ans = 1;

    while (left <= right) {
        ll mid = (left + right) / 2;
        if (check(mid)) {
            ans = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

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

复杂度

先对区间排序，复杂度为 $O(M\log M)$ 。

每次判定扫描所有区间，复杂度为 $O(M)$ 。

坐标最大到 $10^{18}$ ，二分次数约 60 次，所以总时间复杂度为 $O(M\log M+M\log V)$ ，其中 $V$ 是坐标范围。

空间复杂度为 $O(M)$ 。

总结

本题的关键是把“最大化最小距离”转成二分答案。

判定函数只需要一个贪心原则：每头牛尽量往左放。这样既不影响已经满足的距离，也给后面的牛留下最多空间。

目录

题意

思路

代码

复杂度

总结