B1908 【基础】伐木工
大约 2 分钟
B1908 【基础】伐木工
【算法】 二分答案
【C++】 二分、long long
【难度】 普及/提高−
一、题目简述
有 棵树,第 棵树高度为 。伐木工选择一个锯片高度 ,对于每棵树:
- 如果 ,能获得 米木材
- 如果 ,不获得木材
给定目标木材总量 ,求能获得至少 米木材的最大锯片高度 。
数据范围:,,。
二、解题思路
1. 为什么能用二分
单调性:锯片高度 越高,锯掉的木材越少。如果高度为 时能获得 ≥ 米木材,那么任何小于 的高度也能满足(锯得更低,木材更多)。如果 不行,更大的 更不行。
判定结果从"能"变为"不能",单调切换,可以二分。
2. check 函数设计
check(H):遍历所有树,累加 。若总和 ≥ 则可行。
注意:,,木材总和可能超过 int 范围,使用 long long。
3. 二分范围
- 左边界:(把树全锯掉得到最多木材)
- 右边界:(锯片比最高的树还高,得 0 木材)
4. 手动模拟
树高 ,:
| 锯片高度 H | 树1(20) | 树2(15) | 树3(10) | 树4(17) | 总木材 | 是否 ≥ 7 |
|---|---|---|---|---|---|---|
| 15 | 5 | 0 | 0 | 2 | 7 | ✅ |
| 16 | 4 | 0 | 0 | 1 | 5 | ❌ |
答案 = 15。
5. 输入优化
最大到 ,建议使用 scanf 代替 cin 以提高读取速度(不使用 ios::sync_with_stdio 的情况下)。
三、参考代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
long long h[N];
long long n, M;
bool check(long long H) {
long long sum = 0;
for (int i = 1; i <= n; i++)
if (h[i] > H) sum += h[i] - H;
return sum >= M;
}
int main() {
scanf("%lld%lld", &n, &M);
long long maxH = 0;
for (int i = 1; i <= n; i++) {
scanf("%lld", &h[i]);
maxH = max(maxH, h[i]);
}
long long l = 0, r = maxH, ans = 0;
while (l <= r) {
long long mid = (l + r) / 2;
if (check(mid)) { ans = mid; l = mid + 1; }
else r = mid - 1;
}
cout << ans << endl;
return 0;
}四、复杂度分析
- 时间复杂度:。每次
check遍历 棵树 ,二分范围与最大树高相关,约 31 次迭代()。 - 空间复杂度:,存储树高数组。
