【算法通关指南：算法基础篇】二分答案专题：1.木材加工 2.砍树

🔥小龙报：个人主页
🎬作者简介：C++研发，嵌入式，机器人方向学习者
❄️个人专栏：《算法通关指南 》
✨ 永远相信美好的事情即将发生

文章目录

• 前言
• 一、二分答案
• 二、二分答案经典算题
  • 2.1 木材加工
    • 2.1.1题目
    • 2.1.2 算法原理
    • 2.1.3 代码
  • 2.2 砍树
    • 2.2.1 题目
    • 2.2.2 算法原理
    • 2.2.3 代码
• 总结与每日励志

前言

二分答案是算法竞赛与笔试中极具技巧性的高分解法，核心思路是将复杂求解转化为简洁的二分+判定，专门解决「最大值最小」「最小值最大」等经典问题。本文从原理到实战，结合两道高频例题，带你从零掌握二分答案的核心逻辑与代码模板，轻松搞定同类题型。

一、二分答案

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

二、二分答案经典算题

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情况下切几段 LLcacl(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]; int l =0, r =1e8;while(l < r){LL mid =(l + r +1)/2;if(cacl(mid)>= k) l = mid;else r = mid -1;} cout << l << endl;return0;}

2.2 砍树

2.2.1 题目

链接：砍树

2.2.2 算法原理

设伐木机的高度为H ，能得到的木材为C 。根据题意，我们可以发现如下性质，：
• 当H 增大的时候，C 在减小。
• 当H 减小的时候，C 在增大。
那么在整个「解空间」里面，设最终的结果是ret ，于是有：
• 当H ≤ ret 时C>=M ， 也就是「伐木机的高度」大于等于「最优高度」时，能得到的木材「大于等于」M 。
• 当H > ret 时C < M ， 也就是「伐木机的高度」小于等于「最优高度」时，能得到的木材「小于」M 。

2.2.3 代码

//EKO/ 砍树 #include <iostream> using namespace std; const int N=1e6+10; typedef long long LL;LL a[N],n,m;LLcacl(LL mid){LL ret =0;for(int i =1; i <= n; i++){if(a[i]- mid >0) ret += a[i]- mid;}return ret;} int main(){ cin >> n >> m;for(int i =1; i <= n; i++) cin >> a[i];LL l =1, r =2e9;while(l < r){LL mid =(l + r +1)/2;if(cacl(mid)>= m) l = mid;else r = mid -1;} cout << l << endl;return0;}

总结与每日励志

✨二分答案的关键，是抓住解空间的二段性，通过二分缩小范围、用判断函数验证合法性，思路清晰、效率极高。掌握这一思维，不仅能拿下算法题，更能学会用逻辑拆解难题。前路漫漫亦有收获，坚持刷题、稳步进阶，永远相信美好的事情即将发生，你付出的每一份努力，都在为更优秀的自己铺路。 永远相信美好的事情即将发生