🔥小龙报：个人主页 🎬作者简介：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情况下切几段
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];
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;
return 0;
}
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;
LL cacl(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;
return 0;
}
总结与每日励志
✨二分答案的关键，是抓住解空间的二段性，通过二分缩小范围、用判断函数验证合法性，思路清晰、效率极高。掌握这一思维，不仅能拿下算法题，更能学会用逻辑拆解难题。前路漫漫亦有收获，坚持刷题、稳步进阶，永远相信美好的事情即将发生，你付出的每一份努力，都在为更优秀的自己铺路。 永远相信美好的事情即将发生 
