为什么?关于二分的问题

P1525 [NOIP2010 提高组] 关押罪犯

考虑l=1,r=2 当check()==false时,r变为0
by return_TLE @ 2023-11-01 20:47:14


@[Twiter_ln](/user/188970)
by return_TLE @ 2023-11-01 20:49:01


@[return_TLE](/user/912241) 当 $L=1$,$R=2$ 时,$mid=1$。 如果 $check(mid=1)==false$ ,那么不应该是:$L→mid+1 = 2?$ 最终判定 答案 $ans=2$ ,哪里挂了? 疑惑.jpg
by Twiter_ln @ 2023-11-02 15:14:48


@[Twiter_ln](/user/188970) 哦,应该是,当check=true时会出现问题。
by return_TLE @ 2023-11-02 19:12:49


@[return_TLE](/user/912241) OK那如果是 $r=mid$ 而不是 $r=mid-1$ 就过了
by Twiter_ln @ 2023-11-02 20:51:05


@[Twiter_ln](/user/188970) 应该是
by return_TLE @ 2023-11-02 20:59:12


@[return_TLE](/user/912241) 不太对啊,如果当 $mid = 1$ 时 是可行的, $r→mid-1=0$ ,最小解 不就是 $ans=mid=1$ 吗?
by Twiter_ln @ 2023-11-06 09:48:18


@[Twiter_ln](/user/188970) 60 $pts$ 的代码改成 $while(l<=r)$ 就可以了
by 睿智的憨憨 @ 2023-11-13 16:24:04


@[睿智的憨憨](/user/368032) 为啥本来的不对...?
by Twiter_ln @ 2023-11-13 16:26:38


@[Twiter_ln](/user/188970) 因为区间 $[l,r]$ 表示你现在正在判断 $[l,r]$ 内是否有答案,如果你在 $l=r$ 时退出循环,那么你就没有判断 $l$ 到底是不是答案。
by 睿智的憨憨 @ 2023-11-13 16:37:37


|