<----点个赞吧QwQ

一、二分答案简介

二分答案，从名字可知，它是二分，并且二分的是答案。

二、二分的基本概念

这里给出两个模板，在不同情况使用：
把区间划分成$[l,mid]$和$[mid+1,r]$：

while (l < r) {
    int mid = l + r >> 1;   //即除以2下取整
    if (check (mid)) l = mid + 1;
    else r = mid;
}

把区间划分成$[l,mid-1]$和$[mid,r]$：

while (l < r) {
    int mid = l + r + 1 >> 1;   //要注意+1，否则会超市
    if (check (mid)) l = mid;
    else r = mid - 1;
}

这两个模板，就是看你怎么划分来选择的。
这里还有一个模板，有的时候也可以用上：

while (l <= r) {
    int mid = l + r >> 1;
    if (check (mid)) l = mid + 1;
    else r = mid - 1;
}

这里还有一个实数二分，跟整数二分差不多：

while (r - l > EPS) {   //EPS是精度不要太小，否则会炸(TLE)
    double mid = (l + r) / 2;
    if (check (mid)) l = mid;
    else r = mid;
}

注意，这里所有的赋值语句，即改变区间的赋值，都是可以交换的！！！

三、经典例题

题目链接

思路

这道题就是裸的二分，直接上代码

代码

#include <iostream>
using namespace std;
const int N = 1000010;
int n,m;
int a[N];
int main () {
    cin >> n >> m;
    for (int i = 1;i <= n;i++) cin >> a[i];
    for (int i = 1;i <= m;i++) {
        int x;
        cin >> x;
        int l = 1,r = n;
        while (l < r) {
            int mid = l + r >> 1;
            if (a[mid] >= x) r = mid;   //如果当前点是满足条件的，那么答案可以更小，并且mid也有可能成为答案，所以要写r = mid
            else l = mid + 1;   //可以直接对应过来
        }
        if (a[l] != x) return -1;
        cout << l << ' ';
    }
    return 0;
}

题目链接

思路

二分答案，必须要有单调递增的事物（或者具有二分性，即答案的一侧都是不满足条件的，答案的另一侧都是满足答案的），这里好像没有单调递增的数据啊？
这里其实有一个隐含条件：这里的三次函数是递增函数
所以我们二分一下答案，找到最接近结果的答案。
这里题目中还有一个提示（其实是高中数学的必备知识）：记方程$f(x) = 0$，若存在$2$个数$x_1$和$x_2$，且$x_1 < x_2$如果满足$f(x_1) \times f(x_2) < 0$，则在 ($x_1$, $x_2$) 之间一定有一个根。

代码

#include <bits/stdc++.h>
using namespace std;
double a,b,c,d;
double l,r,mid,x1,x2;
double f (double x) {
    return a*x*x*x+b*x*x+c*x+d;
}
int main () {
    cin >> a >> b >> c >> d;
    for (int i = -100;i <= 100;i++) {
        l = i,r = i+1;
        x1 = f (l),x2 = f (r);
        if (x1 == 0) printf ("%.2lf ",l);
        if (x1*x2 < 0) {
            while (r-l >= 0.001) {
                mid = (l+r)/2;
                if (f(mid)*f(r) <= 0) l = mid;
                else r = mid;
            }
            printf ("%.2lf ",r);
        }
    }
    return 0;
}

题目链接

思路

我们直接二分锯子的高度，最大的一个就是答案。

代码

#include <iostream>
using namespace std;
typedef long long LL;
const int N = 1e6+10;
int n,m;
int a[N];
bool check (int x) {
    LL sum = 0;
    for (int i = 1;i <= n;i++) sum += max (a[i]-x,0);
    return sum >= m;
}
int main ()  {
    cin >> n >> m;
    for (int i = 1;i <= n;i++) cin >> a[i];
    int l = 0,r = N;
    while (l < r) {
        int mid = l + r + 1 >> 1;   //记得+1
        if (check (mid)) l = mid;   //如果当前点合法，那么答案可以更大，并且mid也有可能成为答案，所以l = mid
        else r = mid - 1;   对应过来的
    }
    cout << l << endl;
    return 0;
}

题目链接

题解链接