标签：二分 int Luogu mid 答案 check
-
二分答案：
-
基本要点：
- 二分答案就是将暴力找答案的过程变为二分找答案
- 将最优化问题转变为可行性问题
- 二分的答案要求有界性/单调性/二段性
- 主要用于解决最大值最小化/最小值最大化问题
- check函数求y一般用贪心
-
基础模板：
//最大化答案模板：
bool check(int x){
...//计算y
//返回可行区间
return y<=m;//y随答案单调递减
return y>=m;//y随答案单调递增
}
int bianryfind(){
int l=下界-1,r=上界+1;
while(l+1<r){
int mid=r+l>>1;
if(check(mid) l=mid;//左端往大跳
else r=mid;
}
return l;
}
//最小化答案模板：
bool check(int x){
...//计算y
//返回可行区间
return y<=m;//y随答案单调递减
return y>=m;//y随答案单调递增
}
int bianryfind(){
int l=下界-1,r=上界+1;
while(l+1<r){
int mid=r+l>>1;
if(check(mid) r=mid;//右端往小跳
else l=mid;
}
return r;
}
-
题型归纳：
[[Luogu P1182 数列分段 Section II]]
[[Luogu P2678 跳石头]]
[[Luogu P1843 奶牛晒衣服]]
[[Luogu Tracking Segments]]
[[Luogu ABC293F Zero or One]]
标签：二分,
int,
Luogu,
mid,
答案,
check
From： https://www.cnblogs.com/moilip/p/17575100.html