二分本来是无脑的,只是对于答案的检索有些比较麻烦而已,实际上他的本身是不难的。这里给出几个二分的版本
int solve2() {
int l = 0, r = 100;
while(l < r) {
int mid=(l+r)>>1;
if(mid) l = mid+1;
else r = mid - 1;
}
return r;
}
int solve2() {
int l = 0, r = 100;
while(l < r) {
int mid=(l+r)>>1;
if(mid) l = (ans=mid)+1;
else r = mid - 1;
}
return ans;
}
for (int i=1; i<=k; i++){ //k的值取决于L-R的区间大小为2的几次方
int mid=(L+R)>>1;
if (ok(mid)) {ans=mid; L=mid+1;}
else R=mid-1;
}
printf ("%d",ans);
当然,这只是综合了一下,而实际上二分的版本有很多emmm。。。前两种可以说是煞费苦心,然后,很多时候第一发都是WA的。而前两个版本也有很多人写,然后在我们这个队伍里,好像只有我用3。。。。但是他们很多时候二分WA了,我将他们while改成了for结果AC了。。。很尴尬。
但需要注意的是对于第三种情况,L可能大于R,那么mid=(L+R)>>1就会有问题,必须改成mid=L+(R-L)/2。比如UVALive3177–Beijing Guards 但对于while则没有这种顾虑。
还有一些上下界的问题,有些上下界没办法无脑0,inf之类的,比如下界不对的话就会疯狂WA。比如UVALive3177–Beijing Guards
当然有些DL例外,他们不管怎么写都是AC的。。。(什么时候我也能这样啊,羡慕)