题意

有 N 棵树，每棵树有一个高度。锯片高度设为 H 后，只有高于 H 的部分会被锯掉。

要求找到最大的整数高度 H，使得锯下来的木材总长度至少为 M。

思路

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

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

int n;
long long need;
int h[105];

long long wood(int cutHeight) {
    long long sum = 0;
    for (int i = 1; i <= n; i++) {
        if (h[i] > cutHeight) sum += h[i] - cutHeight;
    }
    return sum;
}

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

    cin >> n >> need;
    int maxH = 0;
    for (int i = 1; i <= n; i++) {
        cin >> h[i];
        maxH = max(maxH, h[i]);
    }

    int ans = 0;
    for (int cutHeight = 0; cutHeight <= maxH; cutHeight++) {
        if (wood(cutHeight) >= need) ans = cutHeight;
    }

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

朴素解枚举每个可能高度，计算能得到多少木材。它能帮助理解题意，但正式做法应该利用单调性。

设：

1check(H) = 锯片高度为 H 时，能否得到至少 M 米木材

当 H 越高，锯下来的木材只会越少。因此 check(H) 的结果一定形如：

1true true true ... true false false ...

我们要找的是最后一个 true，也就是最大可行高度。

rbook《二分查找》文章中把这类问题归为“二分答案”：直接求最优值不方便，但给定一个答案可以快速检查。

样例中的高度检查

样例树高为：

120 15 10 17

这张表展示几个高度能得到的木材。

所以最大可行高度是 15。

Python 知识

• sum(max(0, height - cut) for height in heights) 直接表达“每棵树贡献超过锯片的部分”。
• 判定只需要总和，不需要保存每棵树被砍下的长度，因此生成器比列表更合适。
• 上取中点 (left + right + 1) // 2 用于寻找最后一个可行整数，避免只剩两个候选时死循环。
• /home/rainboy/mycode/hugo-blog/content/program_language/python/generator_expression.md：生成器与 sum 的聚合模式。
• /home/rainboy/mycode/hugo-blog/content/program_language/python/oj_input_output_cheatsheet.md：百万级整数输入使用缓冲区读取。

代码

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, need = data[:2]
heights = data[2:2 + n]


def enough(cut):
    return sum(max(0, height - cut) for height in heights) >= need


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

print(left)

复杂度

• 每次检查扫描所有树，复杂度 $O(N)$。
• 二分高度需要 $O(log maxH)$ 次检查。
• 总时间复杂度 $O(N log maxH)$。
• 空间复杂度 $O(N)$。

总结

这题是二分答案入门题。

核心判断是：高度越高，得到木材越少。这个单调性让我们可以在高度范围上二分，找到最高的、仍然能满足需求的锯片高度。

一图流解析

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