[COCI 2011/2012 #5] EKO / 砍树

GitHub跳转原题关系图返回列表

二分锯片高度，扫描树高判断当前高度能否得到至少 M 米木材，寻找最大可行高度。

OJ: luogu

题目 ID: P1873

难度:普及-

标签:二分答案模拟python

创建: 2026-06-18 19:54

更新: 2026-10-27 20:50

后置题目

roj 3592[NOIP2011-提高] 聪明的质监员B 复用了 A 教的「先证阈值越大可行量越少的单调性、再在单调谓词上二分找边界」这一步：A 用它找最后一个 true 得到最大锯片高度，B 把它套到 y(W) 上找第一个 P(W)=(y(W)≤S) 的分界点 W，只额外叠加前缀和把单次求值从 O(n) 区间统计压到 O(n+m)、以及在分界点两侧取最小差值这两个 A 未教的流程。

相似题目

noi_openjudge ch0111-04网线主管同为二分答案+单调判定：网线主管计数可切段数，P1873 求和木材量，判定都是单遍线性聚合比较。luogu P2440木材加工同为最大化可行值的二分答案+线性聚合判定：P1873 求和判断木材达标，P2440 计数判断段数达标，check 可互相套用。OpenJ_Bailian 4135Monthly Expense同为二分答案模板题，P1873 为最简入门，4135 在此基础上加入贪心分段验证。POJ 3122Pie同为基础二分答案模板题，POJ 3122 为实数二分，P1873 为整数二分，对比例题。

题意

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

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

思路

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

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#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;
}

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

设：

text

1check(H) = 锯片高度为 H 时，木材是否**不足** M 米

当 H 越高，锯下来的木材只会越少。因此“木材不足”这个判定随 H 增大一定形如：

text

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

first_true 找的就是第一个 true，也就是第一个失败的高度；它减一就是最后一个可行高度，即最大可行高度。

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

样例中的高度检查

样例树高为：

text

120 15 10 17

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

锯片高度 `H`	得到木材	是否至少 `7`
`14`	`6+1+0+3=10`	是
`15`	`5+0+0+2=7`	是
`16`	`4+0+0+1=5`	否

所以最大可行高度是 15。

Python 知识

sum(max(0, height - cut) for height in heights) 直接表达“每棵树贡献超过锯片的部分”。
判定只需要总和，不需要保存每棵树被砍下的长度，因此生成器比列表更合适。
找“第一个失败位置”用下取中点 (left + right) // 2，右端点取虚拟失败值 max(heights) + 1，最后 -1 得到最后一个可行高度。
/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：百万级整数输入使用缓冲区读取。

代码

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/**
 * 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-10-27 20:50
 */

/* P1873 [COCI 2011/2012 #5] EKO / 砍树 */
/* 二分答案：找最大切割高度，使获得的木材总量 >= need。 */

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

const int MAXN = 1000005;

int n;
long long need;    // 需要的木材量
long long h[MAXN]; // 每棵树的高度

// 切割高度 mid 时得到的木材是否不足 need（即失败）。
// check 单调：false false ... false true true ... true。
bool check(long long mid) {
    long long sum = 0;
    for (int i = 1; i <= n; i++) {
        if (h[i] > mid) {
            sum += h[i] - mid;
            if (sum >= need) 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 >> need;
    long long max_h = 0;
    for (int i = 1; i <= n; i++) {
        cin >> h[i];
        if (h[i] > max_h) max_h = h[i];
    }

    // 第一个失败位置；max_h + 1 是虚拟失败位置（锯片高过所有树，木材为 0）。
    // 答案 = 失败位置 - 1，即最后一个可行高度。
    long long fail_pos = first_true(0, max_h + 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
21
22
23
24
25
26
27
28import 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


def check(cut):
    """切割高度 cut 是否失败（木材不足 need）。false ... false true ... true"""
    return not enough(cut)


# 在 [0, max + 1] 中找第一个失败位置，max + 1 是虚拟失败位置。
# 答案 = 失败位置 - 1，即最后一个可行高度。
left, right = 0, max(heights) + 1
while left < right:
    middle = (left + right) // 2
    if check(middle):
        right = middle
    else:
        left = middle + 1

print(left - 1)

复杂度

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

总结

这题是二分答案入门题。

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

一图流解析

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

P1873 [COCI 2011/2012 #5] EKO / 砍树

题目描述

伐木工人 Mirko 需要砍 $M$ 米长的木材。对 Mirko 来说这是很简单的工作，因为他有一个漂亮的新伐木机，可以如野火一般砍伐森林。不过，Mirko 只被允许砍伐一排树。

Mirko 的伐木机工作流程如下：Mirko 设置一个高度参数 $H$ （米），伐木机升起一个巨大的锯片到高度 $H$ ，并锯掉所有树比 $H$ 高的部分（当然，树木不高于 $H$ 米的部分保持不变）。Mirko 就得到树木被锯下的部分。例如，如果一排树的高度分别为 $20,15,10$ 和 $17$ ，Mirko 把锯片升到 $15$ 米的高度，切割后树木剩下的高度将是 $15,15,10$ 和 $15$ ，而 Mirko 将从第 $1$ 棵树得到 $5$ 米，从第 $4$ 棵树得到 $2$ 米，共得到 $7$ 米木材。

Mirko 非常关注生态保护，所以他不会砍掉过多的木材。这也是他尽可能高地设定伐木机锯片的原因。请帮助 Mirko 找到伐木机锯片的最大的整数高度 $H$ ，使得他能得到的木材至少为 $M$ 米。换句话说，如果再升高 $1$ 米，他将得不到 $M$ 米木材。

输入格式

第 $1$ 行 $2$ 个整数 $N$ 和 $M$ ， $N$ 表示树木的数量， $M$ 表示需要的木材总长度。

第 $2$ 行 $N$ 个整数表示每棵树的高度。

输出格式

$1$ 个整数，表示锯片的最高高度。

输入输出样例 #1

输入 #1

text

1
24 7
20 15 10 17

输出 #1

text

输入输出样例 #2

输入 #2

text

1
25 20
4 42 40 26 46

输出 #2

text

说明/提示

对于 $100\%$ 的测试数据， $1\le N\le10^6$ ， $1\le M\le2\times10^9$ ，树的高度 $\le 4\times 10^5$ ，所有树的高度总和 $>M$ 。

[COCI 2011/2012 #5] EKO / 砍树

目录

题意

思路

样例中的高度检查

Python 知识

代码

Python 代码

复杂度

总结

一图流解析