「一本通 1.2 例 1」愤怒的牛

题目描述

农夫 John 的畜栏有 $N$ 个编号为 $x_i$ 的隔间（ $2 \le N \le 10^5$ ， $0 \le x_i \le 10^9$ ），要把 $C$ 头牛（ $2 \le C \le N$ ）分到互不相同的隔间里，使任意两头牛之间距离的最小值尽量大。求这个最大的最小距离。

输入：第一行 $N,C$ ，接下来 $N$ 行每行一个 $x_i$ ；输出：一个整数，即最大的最小距离。样例：输入 5 3 / 1 2 8 4 9，输出 3。

思路

最小值最大，转为二分答案：判定「间距至少 $d$ 能否放下 $C$ 头牛」。把位置排序后贪心，第一头牛放最左，之后每头都放第一个距离上一头至少 $d$ 的隔间，能放下 $C$ 头即可行。 $d$ 越小越容易放下，可行性关于 $d$ 单调，于是在 $[1,(s_N-s_1)/(C-1)]$ 上二分最大的可行 $d$ 。

参考代码

Python 版：

python

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#!/usr/bin/env python3
# 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-09-30 10:09
# update_at: 2026-09-30 10:09

import sys


def can_place(stalls: list[int], cows: int, dist: int) -> bool:
    """间距至少 dist 时能否放下 cows 头牛（贪心：第一头放最左，之后每头都放能塞下的最左隔间）。

    每头牛都尽量往左压，给后面的牛留出最大剩余空间；若这种最省地盘的方式都放不下，
    其它摆法只会更挤，所以贪心的可行性等价于真正的可行性。
    """
    placed = 1     # 最左隔间必放一头，这是留给后面牛最多余量的摆法
    last = stalls[0]
    for pos in stalls:
        if pos - last >= dist:      # 找到下一头能放的隔间，越靠左越好
            last = pos
            placed += 1
    return placed >= cows


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, c = next(data), next(data)
    stalls = sorted(next(data) for _ in range(n))

    # 题面只保证 0 <= xi <= 1e9，没保证位置互不相同。若不同位置不足 c 个，
    # 必有一对牛同处一室，最小距离只能是 0，下面的 [1, hi] 二分区间会漏掉这个答案。
    if len(set(stalls)) < c:
        print(0)
        return

    # 答案就是"最大可行间距"，可行性关于 dist 单调（dist 越小越容易放下），故可二分。
    # 上界取把 c 头牛均摊到两端之间：间距再大，光是首尾两头就超过总跨度了。
    lo, hi = 1, (stalls[-1] - stalls[0]) // (c - 1)
    while lo < hi:
        mid = (lo + hi + 1) >> 1        # 上取整，配合 lo = mid 避免死循环
        if can_place(stalls, c, mid):
            lo = mid                    # mid 可行，答案不小于 mid
        else:
            hi = mid - 1
    print(lo)


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

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/**
 * 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-10-05 23:30
 * update_at: 2026-10-05 23:30
 */
#include <cstdio>
#include <algorithm>
using namespace std;

typedef long long ll;

const int MAXN = 100005;

ll n;               // 隔间数量
ll c;               // 牛的数量
ll stall[MAXN];     // stall[i] 表示第 i 个隔间的位置（排序后使用）

// 判定间距至少为 dist 时能否放下 c 头牛。
// 贪心：第一头牛放在最左隔间，之后每头都放在第一个距离上一头牛至少 dist 的隔间。
// 每头牛都尽量往左压，给后面的牛留出最大剩余空间，因此这种摆法可行等价于真正可行。
bool can_place(ll dist) {
    ll placed = 1;          // 最左隔间必放一头
    ll last = stall[1];     // 上一头牛所在的隔间位置
    for (ll i = 2; i <= n; i++) {
        if (stall[i] - last >= dist) {
            last = stall[i];
            placed++;
        }
    }
    return placed >= c;
}

int main() {
    scanf("%lld %lld", &n, &c);
    for (ll i = 1; i <= n; i++) {
        scanf("%lld", &stall[i]);
    }
    sort(stall + 1, stall + n + 1);

    // 题面只保证 0 <= xi <= 1e9，没保证位置互不相同。
    // 若不同位置不足 c 个，必有一对牛同处一室，最小距离只能是 0，
    // 下面的 [1, hi] 二分区间覆盖不到这个答案。
    ll distinct = 1;
    for (ll i = 2; i <= n; i++) {
        if (stall[i] != stall[i - 1]) {
            distinct++;
        }
    }
    if (distinct < c) {
        printf("0\n");
        return 0;
    }

    // 可行性关于 dist 单调（dist 越小越容易放下），所以二分最大的可行间距。
    // 上界：c 头牛两两间距 >= d 时首尾至少隔开 (c-1)*d，不超过总跨度。
    ll lo = 1;
    ll hi = (stall[n] - stall[1]) / (c - 1);
    while (lo < hi) {
        ll mid = (lo + hi + 1) / 2;   // 上取整，配合 lo = mid 避免死循环
        if (can_place(mid)) {
            lo = mid;
        } else {
            hi = mid - 1;
        }
    }
    printf("%lld\n", lo);
    return 0;
}

「一本通 1.2 例 1」愤怒的牛

目录

题目描述

思路

参考代码