二分有问题 这样的话答案不可能取到1
改成如下
```c++
int l=1,r=m;
while(l<r)
{
int mid=(l+r)>>1;
if(check(mid)) l=mid+1;
else r=mid;
}
printf("%d",l);
return 0;
```
亲测可A
by smarthehe @ 2019-04-21 17:15:00
@[Eternal_Sz](/space/show?uid=102003)
by smarthehe @ 2019-04-21 17:15:11
@[smarthehe](/space/show?uid=103732)
感谢感谢
不过好像还有个问题
二分的模板我是比着算法竞赛的一本书上写的
书上说一般只有
```
while(l<r){
int mid=(l+r)>>1;
if(a[mid]>=x) r=mid;
else l=mid+1;
}
return a[l];
```
```
while(l<r){
int mid=(l+r)>>1;
if(a[mid]<=x) l=mid;
else r=mid-1;
}
return a[l];
```
那这种写法有什么区别呢??
现在又多了一个这种写法
麻烦dalao帮忙区分一下吧
蒟蒻搞不太懂啊
by Eternal_Sz @ 2019-04-21 17:33:54
当然是选择线段树啊(逃
by 不准睡觉 @ 2019-04-21 17:37:22
@[Eternal_Sz](/space/show?uid=102003)
这里还有一份正确的二分:
```c++
int l=0,r=m;
while(l<r)
{
int mid=(l+r+1)>>1;
if(check(mid)) l=mid+1;
else r=mid;
}
printf("%d",l+1);
return 0;
```
两个算法的二分对象不同:
第一个,二分首次不满足要求的位置
第二个,二分最后一次满足要求的位置
本质上二分的对象是不一样的,你可以自己理解一下
by smarthehe @ 2019-04-21 18:01:20
@[Eternal_Sz](/space/show?uid=102003)
你的算法没有问题,二分的是最后一次满足要求的位置
错因只是把`l`设成了`1`
这样的话二分范围不全,因为有可能第一次就不满足要求了,这样应该结果是`0`,而你的二分不可能返回一个`0`
by smarthehe @ 2019-04-21 18:03:23