2025 8 4 XP02-1

二分答案

1、确定单调性/二段性
二段性题目：找分界点

2、二分模板
int l=答案可能的最小值, r=答案可能的最大值;
int ans=0;
while(l<=r){
int mid=(l+r)/2;
if(check(mid)){
ans=mid;
// 求最大值 l=mid+1;
// 求最小值 r=mid-1;
}
else{
// 求最大值 r=mid-1;
// 求最小值 l=mid+1;
}
}

3、check 函数
具体问题具体分析
需要检查当前二分的答案是否符合题目要求
明确所有变量代表的意义
最后和什么比? 题目中的某一个定值

4、如何提升自己二分答案的能力