二分答案算法详解：木材加工与砍树问题

前言

二分答案是算法竞赛与笔试中极具技巧性的高分解法，核心思路是将复杂求解转化为简洁的二分 + 判定，专门解决「最大值最小」「最小值最大」等经典问题。

一、二分答案

二分答案准确来说，应该叫做「二分答案 + 判断」。 二分答案可以处理大部分「最大值最小」以及「最小值最大」的问题。如果「解空间」在从小到大的「变化」过程中，「判断」答案的结果出现「二段性」，此时我们就可以「二分」这个「解空间」，通过「判断」，找出最优解。

二、二分答案经典算题

2.1 木材加工

2.1.1 题目

链接：木材加工

2.1.2 算法原理

2.1.3 代码

//木材加工
#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;
}

int main(){
    cin >> n >> k;
    for(int i = 1; i <= n; i++) cin >> a[i];
     l = , r = ;
    (l < r){
        LL mid =(l + r )/;
        ((mid)>= k) l = mid;
         r = mid ;
    }
    cout << l << endl;
     ;
}