本篇內(nèi)容講解二分答案，并通過實例分析和解決問題，在一些解題中，二分答案往往在一個單調(diào)閉區(qū)間上進行，也就是說，二分答案最后得到的答案應(yīng)該是一個確定值，而不是像搜索那樣出現(xiàn)多解的情況。那么什么時候適用二分答案呢？下面我們詳細(xì)為大家說說，并且通過練習(xí)題講解，幫助大家學(xué)習(xí)和應(yīng)用。

一、簡介 

二分答案就是就相當(dāng)于枚舉答案，并判斷答案是否合法，如果合法，就將答案進一步靠近，如果不合法，就往前判斷。對于每個次判斷，即使復(fù)雜度較高，也可以穩(wěn)過。

（1）應(yīng)用前提：二分答案要求滿足條件的答案單調(diào)，否則你就不能確定下一次查找答案所在的區(qū)間；

（2）二分答案可以用在什么地方呢？顯然，每次判斷都會返回一個布爾值，這個值判斷這個答案是大了還是小了，所以只有答案具有單調(diào)性的時候才可以用二分答案。還可以通過找“最大值最小”或“最小值最大”這種字眼來判斷能不能使用二分。

（3）常規(guī)做法：1. 發(fā)現(xiàn)答案存在單調(diào)性；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個投票箱中的最大票數(shù)最小

分析：每一個城市的人均勻的投到每個投票箱，才會使得這個城市的最大票數(shù)最小，此題的答案是票數(shù)，條件是每個城市至少分配一個投票箱，如果最大票數(shù)為mid 滿足條件，要使最大票數(shù)最小，那么肯定在小于mid的區(qū)間繼續(xù)查找答案

代碼：

#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個朋友，使得每人拿到的一樣大，且每個人只能拿一整塊，求每個人能拿到的最大值

答案：每個人拿到的餡餅的最大值，條件：每人拿到的一樣大，且每個人只能拿一整塊；可以選擇二分半徑的區(qū)間，通過半徑計算答案，根據(jù)條件每人只能拿一整塊，那么每塊餡餅最多能分成(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;
}

三、總結(jié)

（1）判斷答案是否單調(diào)

（2）確定二分區(qū)間，找準(zhǔn)條件

（3）判斷mid是否滿足條件

（4）更新答案區(qū)間

（5）邊界為浮點時，循環(huán)條件要控制精度，更新區(qū)間不能+1