每日c/c++题 备战蓝桥杯（洛谷P1873 EKO砍树问题详解）

洛谷P1873 EKO砍树问题详解

题目描述

P1873 EKO砍树 要求在保证所有树木高度不低于H的情况下，通过砍伐使得总木材量至少为M，求最大可能的H值。

输入格式：

• 第1行：N（树木数量），M（需求木材量）
• 第2行：N个整数表示每棵树的高度

输出格式：

• 满足条件的最大H值

算法思路

问题分析

本题核心是在离散范围内寻找最大可行解，具有典型的二分查找特征：

1. 单调性：当H增大时，可获得的木材总量单调不增
2. 决策可行性：对于任意H值，可在O(N)时间内验证是否满足总木材量≥M

二分法适用性

• 搜索范围：[0, max_height]（max_height为原始最高树高）
• 目标：找到最大的H使得总木材量≥M
• 时间复杂度：O(N log max_height)，可处理1e6级数据

代码解析与优化

原始代码分析

用户提供的代码已实现核心逻辑，但存在两个优化点：

1. 右边界冗余：直接使用2e9作为右边界，未利用输入数据特性
2. 数组遍历方式：可从后向前遍历优化缓存命中率

优化后代码

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

long long N, M;
vector<long long> trees;

bool check(long long H) {
    long long sum = 0;
    for (long long h : trees) {
        if (h > H) sum += h - H;
        if (sum >= M) return true;  // 提前终止优化
    }
    return sum >= M;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> N >> M;
    trees.resize(N);
    long long max_h = 0;
    
    for (auto& h : trees) {
        cin >> h;
        max_h = max(max_h, h);
    }
    
    long long L = 0, R = max_h;
    long long ans = 0;
    
    while (L <= R) {
        long long mid = L + (R - L) / 2;
        if (check(mid)) {
            ans = mid;
            L = mid + 1;
        } else {
            R = mid - 1;
        }
    }
    
    cout << ans << endl;
    return 0;
}

关键优化说明

1. 动态右边界：

   long long max_h = *max_element(trees.begin(), trees.end());
   

   通过预处理获取最大树高，将二分范围缩小到实际可能区间

2. 提前终止优化：

   if (sum >= M) return true;  // Check函数内
   

   当累计木材量已满足需求时立即返回，减少不必要的计算

3. 输入优化：

   ios::sync_with_stdio(false);
   cin.tie(nullptr);
   

   关闭C++流同步，加速大数据量输入

复杂度分析

注意事项

1. 数据类型：

   • 使用long long防止大数溢出（M可达1e18）
   • 输入输出时注意类型匹配

2. 边界条件：

   • 当M=0时，H可取最大值（需单独处理）
   • 当所有树高<H时，总木材量为0

3. 精度问题：

   • 本题H为整数，无需处理浮点精度
   • 若改为实数版本，需设置合适终止条件

测试样例

样例输入1：

4 7
20 15 10 17

执行过程：

• 初始范围：[0, 20]
• 二分过程：
  • mid=10 → sum=20+15+10+17-4*10=22 ≥7 → 尝试更大H
  • mid=15 → sum=20+17-2*15=7 ≥7 → 尝试更大H
  • mid=17 → sum=20+17-2*17=3 <7 → 回退
• 最终结果：15

样例输出1：

15

扩展思考

1. 变种问题：

   • 若要求总木材量恰好等于M，如何处理？
   • 若H可取实数，如何修改代码？

2. 实际应用：

   • 资源分配问题（如水库蓄水高度）
   • 生产调度中的最小成本问题

3. 算法对比：

   • 与三分法的区别：三分法适用于单峰函数，本题具有严格单调性

总结

本题通过二分法将看似复杂的优化问题转化为简单的可行性判断，关键点在于：

1. 准确识别问题的单调性
2. 高效实现可行性检查函数
3. 合理设置二分边界

掌握这种思维模式，可以解决一类"最大最小值"问题（Maximize the Minimum Value），是算法竞赛中的重要技巧。