二分答案算法实例讲解

本篇内容讲解二分答案，并通过实例分析和解决问题，在一些解题中，二分答案往往在一个单调闭区间上进行，也就是说，二分答案最后得到的答案应该是一个确定值，而不是像搜索那样出现多解的情况。那么什么时候适用二分答案呢？下面我们详细为大家说说，并且通过练习题讲解，帮助大家学习和应用。

一、简介 

二分答案就是就相当于枚举答案，并判断答案是否合法，如果合法，就将答案进一步靠近，如果不合法，就往前判断。对于每个次判断，即使复杂度较高，也可以稳过。

（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