P1873 砍树
对应章节：三、解题方法论：从题意到代码 → （七） 把最优化改成可行性判断；五、数据结构与算法 → （十） 二分与三分搜索。
（一） 任务与输出目标
找出能取得至少 M 木材的最高整数锯片高度。
（二） 建模与推导
固定高度 H，每棵树贡献 max(0,height-H)。升高锯片时每棵贡献不增，所以足够木材的高度是一段连续前缀。二分最后一个可行高度：中点可行就保留中点及右侧，不可行就删掉中点及右侧。取上中点，使只有两个候选时仍能推进。
（三） 手算与过程
20,15,10,17，需要 7：H=15 得 5+2=7；H=16 只得 4+1=5，答案 15。
（四） 带注释实现
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
void solve() {
int n;
int need;
cin >> n >> need;
vector<int> a(n);
int low = 0, high = 0;
for (auto& x : a) {
cin >> x;
high = max(high, x);
}
while (low < high) {
int mid = low + (high - low + 1) / 2, wood = 0;
for (int x : a)
if (x > mid)
wood += x - mid; // 累加锯下的部分。
if (wood >= need)
low = mid;
else
high = mid - 1;
}
cout << low << '\n';
}
signed main() {
ios::sync_with_stdio(false); // 关闭同步，使用 cin 与 cout 完成输入输出。
cin.tie(0), cout.tie(0);
int T = 1; // 本题读入一组数据。
// cin >> T; // 题目给出测试组数时开启，并在 solve 中处理一组。
while (T--)
solve();
}（五） 复杂度
最高树高 H，时间 \(O(n\log(H+1))\)，空间 \(O(n)\)。