二分答案专题实战
二分答案，准确来说应该叫做「二分答案 + 判断」。这是一种极具技巧性的高分解法，专门解决「最大值最小」「最小值最大」等经典问题。核心思路是将复杂求解转化为简洁的二分查找加判定函数。
如果解空间在从小到大的变化过程中，判断答案的结果出现二段性（单调性），此时我们就可以二分这个解空间，通过判断找出最优解。
木材加工
题目描述
解题思路
这道题要求我们切出至少 k 段长度为 x 的木材，求 x 的最大值。随着切割长度 x 的增加，能切出的段数会减少；反之亦然。这种单调性正是二分答案的基础。
我们需要定义一个判定函数 check(x)，计算当切割长度为 x 时，总共能切出多少段。如果段数大于等于 k，说明 x 可能还可以更大，尝试向右搜索；否则向左搜索。
注意边界情况，l 从 0 开始，r 设为足够大的值（如 1e8）。
代码实现
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
typedef long long LL;
LL a[N], n, k;
// 计算在切割长度为 x 情况下能切几段
LL cacl(LL x) {
LL cnt = 0;
for (int i = 1; i <= n; i++) {
cnt += a[i] / x;
}
return cnt;
}
{
cin >> n >> k;
( i = ; i <= n; i++) cin >> a[i];
l = , r = ;
(l < r) {
LL mid = (l + r + ) / ;
((mid) >= k) l = mid;
r = mid - ;
}
cout << l << endl;
;
}
