题意

给出 $n$ 根原木和目标段数 $k$。 要求把每根原木切成若干段长度相同的整数木段，并且总段数不少于 $k$。 输出能切出的最大长度。

思路

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

在小数据上，我们可以把段长 $l$ 从小到大往上试，只要它还可行就继续增大，直到第一次不可行。 前一个可行值就是答案。

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

const int MAXN = 100000 + 5;

int n;
long long k;
long long wood[MAXN];

bool check(long long len) {
    long long cnt = 0;
    for (int i = 1; i <= n; i++) {
        cnt += wood[i] / len;
        if (cnt >= k) return true;
    }
    return false;
}

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

    cin >> n >> k;
    long long mx = 0;
    for (int i = 1; i <= n; i++) {
        cin >> wood[i];
        mx = max(mx, wood[i]);
    }

    long long ans = 0;
    while (ans + 1 <= mx && check(ans + 1)) {
        ans++;
    }

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

这个朴素解的问题在于，段长的范围最大可以到 $10^8$，直接枚举会太慢。 但它已经把问题拆成了两个部分：

1. 固定一个段长 $l$，怎么判断它能不能切出足够多的木段；
2. 如何更快地找到最大的可行 $l$。

对固定的 $l$，每根木头能切出的段数就是 $floor(L_i / l)$。 把所有木头的贡献加起来，就能得到总段数。

因为段长越大，总段数越少，所以可行性具有单调性。 于是可以对段长二分，找到最大的可行值。

Python 知识

• sum(log // length for log in logs) 用整除计算每根原木能贡献的段数，再直接聚合。
• 生成器不会创建“每根木头的段数”中间列表。
• 二分从 0 开始，因此即使 1cm 也切不出，答案仍能自然落在 0。
• /home/rainboy/mycode/hugo-blog/content/program_language/python/generator_expression.md：一次性聚合使用生成器。
• /home/rainboy/mycode/hugo-blog/content/program_language/python/oj_input_output_cheatsheet.md：纯整数 token 的快速读取。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21import sys


data = list(map(int, sys.stdin.buffer.read().split()))
n, needed_pieces = data[:2]
logs = data[2:2 + n]


def enough(length):
    return sum(log // length for log in logs) >= needed_pieces


left, right = 0, max(logs)
while left < right:
    middle = (left + right + 1) // 2
    if enough(middle):
        left = middle
    else:
        right = middle - 1

print(left)

复杂度

check(len) 需要扫描所有木头，复杂度是 $O(n)$。 二分段长需要 $O(log max(L_i))$ 次检查。

所以总时间复杂度是 $O(n log max(L_i))$，空间复杂度是 $O(n)$。

总结

这题是标准的“二分答案”。 关键在于把“能不能切出至少 $k$ 段”写成一个单调判断函数，然后对段长二分。

一图流解析

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