本篇内容讲解二分答案，并通过实例分析和解决问题，在一些解题中，二分答案往往在一个单调闭区间上进行，也就是说，二分答案最后得到的答案应该是一个确定值，而不是像搜索那样出现多解的情况。那么什么时候适用二分答案呢？下面我们详细为大家说说，并且通过练习题讲解，帮助大家学习和应用。
一、简介
二分答案就是就相当于枚举答案，并判断答案是否合法，如果合法，就将答案进一步靠近，如果不合法，就往前判断。对于每个次判断，即使复杂度较高，也可以稳过。
（1）应用前提：二分答案要求满足条件的答案单调，否则你就不能确定下一次查找答案所在的区间；
（2）二分答案可以用在什么地方呢？显然，每次判断都会返回一个布尔值，这个值判断这个答案是大了还是小了，所以只有答案具有单调性的时候才可以用二分答案。还可以通过找“最大值最小”或“最小值最大”这种字眼来判断能不能使用二分。
（3）常规做法：1. 发现答案存在单调性；2. 二分答案；3. 检查答案是否可行。
二、实例分析
题目：在n个点中选c个点使得相邻的点之间的最小距离最大，求最大值
分析：暴力选c个点肯定超时，考虑二分答案，这个最大值的范围为[0，点的最大值-最小值]，如果能找出c个使得他们相邻的点之间的最小距离为mid，那么小于mid的答案肯定也满足要求，若不能找到，那么大于mid的答案就更不能找到。
代码：
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MAXN = 1e5+55;
ll n,c;
ll arr[MAXN];
bool check(int mid) //贪心判断mid是否满足要求
{
int num = 1;
int x = arr[1];
for(int i=2; i<=n&&num<c; ++i)
{
if(arr[i]-x>=mid)
{
num++;
x = arr[i];
}
}
return num >= c? true : false;
}
int main()
{
while(cin>>n>>c)
{
for(int i=1; i<=n; ++i)
scanf("%lld",&arr[i]);
sort(arr+1,arr+n+1);
int l = 0;
int r = (int)1e9+99;
int ans = 0;
while(l<=r)
{
int mid = (l+r)>>1;
if(check(mid))
{
ans = mid;
l = mid+1;
}
else r = mid-1;
}
cout<<ans<<endl;
}
return 0;
}（2）求最小的最大值
题目：把B个投票箱分配到n个城市，使得B个投票箱中的最大票数最小
分析：每一个城市的人均匀的投到每个投票箱，才会使得这个城市的最大票数最小，此题的答案是票数，条件是每个城市至少分配一个投票箱，如果最大票数为mid 满足条件，要使最大票数最小，那么肯定在小于mid的区间继续查找答案
代码：
#include <cmath>
#include <cstdio>
#include <iostream>
using namespace std;
const int MAXN = 2e6+66;
int a[MAXN];
int n,b;
bool check(int mid)
{
int m = b;
for(int i=1;i<=n;++i)
{
int tep = (int)ceil(a[i]*1.0/mid);//第i个城市最少需要tep个投票箱
if(m<tep)
return false;
else m -= tep;
}
return true;
}
int main()
{
while(cin>>n>>b)
{
if(n==-1&&b==-1) break;
for(int i=1;i<=n;++i)
{
scanf("%d",&a[i]);
}
int l = 1;
int r = (int)5e6+6;
int ans = 0;
while(l<=r)
{
int mid = (l+r)>>1;
if(check(mid))
{
r=mid-1;
ans = mid;
}
else l = mid+1;
}
cout<<ans<<endl;
}
return 0;
}（3）求满足条件的最大(小)值
题目：将n个馅饼分给f个朋友，使得每人拿到的一样大，且每个人只能拿一整块，求每个人能拿到的最大值
答案：每个人拿到的馅饼的最大值，条件：每人拿到的一样大，且每个人只能拿一整块；可以选择二分半径的区间，通过半径计算答案，根据条件每人只能拿一整块，那么每块馅饼最多能分成(Vi/mid)个，再来判断能否分成 f+1个(自己也要吃一个)
代码：
#include <cmath>
#include <cstdio>
#include <iostream>
using namespace std;
const double eps = 1e-10;
const double pi = 4*atan(1.0);
int n,f,arr[10100];
bool check(double r)
{
double s = r*r;
int num = 0;
for(int i=1; i<=n; ++i)
{
double tep = arr[i]*arr[i];
num += (int)(tep/s);
}
return num >= f+1? true : false;
}
int main()
{
int t;
cin>>t;
while(t--)
{
cin>>n>>f;
for(int i=1; i<=n; ++i)
cin>>arr[i];
double l = 0.0;
double r = 10100.0;
while(fabs(r-l)>eps) //注意精度
{
double mid = (l+r)/2.0;
if(check(mid))
l = mid;
else r = mid;
}
printf("%.4f\n",r*r*pi);
}
return 0;
}三、总结
（1）判断答案是否单调
（2）确定二分区间，找准条件
（3）判断mid是否满足条件
（4）更新答案区间
（5）边界为浮点时，循环条件要控制精度，更新区间不能+1
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：
一点编程也不会写的：零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码？手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程