木材加工

题意

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

思路

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

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

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#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$ ，直接枚举会太慢。但它已经把问题拆成了两个部分：

固定一个段长 $l$ ，怎么判断它能不能切出足够多的木段；
如何更快地找到最大的可行 $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 的快速读取。

代码

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-08-09 06:46
 * update_at: 2026-08-14 19:34
 */

/* P2440 木材加工 */
/* 二分答案：找最大的切割长度，使切出的段数 >= k。 */

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100000 + 5;

int n;
long long k;       // 需要的段数
long long wood[MAXN]; // 每根木材的长度

// 切割长度 mid 时，切出的段数是否 < k（即不可行）。
// check 单调：false false ... false true true ... true。
bool check(long long mid) {
    long long cnt = 0;
    for (int i = 1; i <= n; i++) {
        cnt += wood[i] / mid;
        if (cnt >= k) return false;
    }
    return true;
}

// 在 [l, r] 中查找第一个满足 check(pos) 的位置。
// 要求 check 单调：false false ... false true true ... true。
// 调用时要保证 r 是一个真实或虚拟的可行位置。
long long first_true(long long l, long long r) {
    while (l < r) {
        long long mid = l + (r - l) / 2;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    return l;
}

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];
        if (wood[i] > mx) mx = wood[i];
    }

    // 第一个失败位置；mx+1 是虚拟失败位置（任何木头都切不出 1 段）。
    // 答案 = 失败位置 - 1，即最后一个可行长度；无解时失败位置为 1，答案为 0。
    long long fail_pos = first_true(1, mx + 1);
    cout << fail_pos - 1 << '\n';
    return 0;
}

Python 教学版本：

Python 代码

python

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$ 段”写成一个单调判断函数，然后对段长二分。

一图流解析

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

目录

题意

思路

Python 知识

代码

Python 代码

复杂度

总结

一图流解析