对于二分答案的引述来自：二分查找 & 二分答案 万字详解，超多例题，带你学透二分。_c++二分答案怎么确定是l<r还是l<=r-CSDN博客
概念：
二分答案：答案有一个区间，在这个区间中二分，直到找到最优答案。
什么时候用二分答案？
答案属于一个区间，当这个区间很大时，暴力超时。但重要的是——这个区间是对题目中的某个量有单调性的，此时，我们就会二分答案。每一次二分会做一次判断，看是否对应的那个量达到了需要的大小。
如何判断一个题是不是用二分答案做的呢?
- 答案在一个区间内（一般情况下，区间会很大，暴力超时）
- 直接搜索不好搜，但是容易判断一个答案可行不可行
- 该区间对题目具有单调性，即：在区间中的值越大或越小，题目中的某个量对应增加或减少
此外，可能还会有一个典型的特征：求...最大值的最小 、 求...最小值的最大。
求...最大值的最小，我们二分答案（即二分最大值）的时候，判断条件满足后，尽量让答案往前来（即：让r=mid）- 同样，
求...最小值的最大时，我们二分答案（即二分最小值）的时候，判断条件满足后，尽量让答案往后走（即：让l=mid）
基于上述思想，来看两道去年XCPC的二分答案的例题。
写在前面：最近这两次训练赛都没看出这是一道二分答案的题，导致这两题都卡了挺久（主要还是连思路都不对），所以回头总结一下二分答案可能的情况，为下次遇到新题时能更快想到二分答案的思路。
The 13th Shandong ICPC Provincial Collegiate Programming Contest
里面的D题 题目链接：Problem - D - Codeforces
题意：对于一个运动员 i ，他的速度是 vi，体重是 wi。如果运动员 j 的体重 wj <= wi，那么运动员 i 可以用原本的速度 vi 背着运动员 j 奔跑。如果 wj > wi，那么速度就变成了 vi - ( wi - wj ) （如果是负数，那么运动员 i 不能背着 j 奔跑），求这个团队奔跑起来后速度最慢的那个人的速度最大值。
思路：求·····最小值的最大，那么我们可以考虑二分答案，套用二分求右边界的模板，重点是如何写check函数，我们可以开两个数组，一个用来存入被背的人数，一个用来存入背别人的人数，被背的人的数组存的是该人的体重，背别人的数组存的是vi+wi-x（x是二分的数，公式由来x=vi+wi-wj），将这两个数组进行降序排序，然后进行比较即可。
代码：
#include<bits/stdc++.h>
#define int long long
#define endl "\n"
#define fi first
#define se second
#define PII pair<int,int>
using namespace std;
const int N=1e5+5;
struct node{
int a,b;
};
node s[N];
int n;
bool cmp1(int x,int y){
return x>y;
}
bool cmp2(int x,int y){
return x>y;
}
bool check(int x){
vector<int> b;//存入被背的人的数量
vector<int> c;//存入背别人的人的数量
for(int i=0;i<n;++i){
if(s[i].a<x){
b.push_back(s[i].b);
}
else c.push_back(s[i].a+s[i].b-x);
}
int lenb=b.size(),lenc=c.size();
if(lenb>lenc) return false;
sort(b.begin(),b.end(),cmp1);
sort(c.begin(),c.end(),cmp2);
for(int i=0;i<lenb;++i){
if(b[i]>c[i]) return false;//当背不下时直接返回flase
}
return true;//全背的下返回true
}
void solve(){
cin >> n;
int l=0,r=0;
for(int i=0;i<n;++i){
cin >> s[i].a >> s[i].b;
r=max(r,s[i].a);
}
r+=1;
while(l<r){//二分求右边界模板
int mid=l+r+1>>1;
if(check(mid)) l=mid;
else r=mid-1;
}
cout << l << endl;
return ;
}
signed main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int t=1;
cin >> t;
while(t--) solve();
return 0;
}The 2023 Guangdong Provincial Collegiate Programming Contest
里面的I题 题目链接：Problem - I - Codeforces
题意：
思路：题目求所有mex（S）的最小非负整数中最大的mex（S），也是和上题一样求····最小值的最大，那么我们也是考虑二分答案，首先看数据范围，我们首先需要状态压缩，由题意可知右边界最大为n*m，同样套用二分求右边界模板，在check函数里面，由题目（i，j）的状态转移只能是向下或者向右，那么我们可以用一个变量k来标记下标，当x（即二分的数）大于a[i][j]时，若k大于j，直接返回false（因为它只能向下或者向右走，那么每次移动的过程不能回头，k即是模拟它当前的下标），若小于等于j更新k等于j，最后若循环结束直接返回true即可。
代码：
#include<bits/stdc++.h>
#define int long long
#define endl "\n"
#define fi first
#define se second
#define PII pair<int,int>
using namespace std;
const int N=1e6+5;
int a[N];
int n,m;
bool check(int x){
int k=0;//标记棋子移动的下标
for(int i=0;i<n;++i)
for(int j=0;j<m;++j){
if(a[i*m+j]<x){//若小于x则需要状态转移
if(k>j) return false;//若k大于j则不满足题意
k=j;
}
}
return true;
}
void solve(){
cin >> n >> m;
for(int i=0;i<n;++i)
for(int j=0;j<m;++j){
cin >> a[i*m+j];//状态压缩
}
int l=0,r=n*m;
while(l<r){
int mid=l+r+1>>1;
if(check(mid)) l=mid;
else r=mid-1;
}
cout << l << endl;
return ;
}
signed main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int t=1;
cin >> t;
while(t--) solve();
return 0;
}