欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

浅谈二分答案

程序员文章站 2024-03-17 17:01:46
...

举个例子:

对于一些问题,它的解满足单调性,即如果x满足条件,则对于任意的 i ( 1<=i<=x) 或 (x <=i <=n) (假设1和n是答案的上下界)都会满足条件。一般遇上这种问题,我们就可以用二分答案来解决。

在不知道二分答案这个东西的时候,我们会这样写:

for (int i = 1; i <= n; i++) {
    if (!check(i)) {
        ans = i - 1;
        break;
    }
}

毫无疑问,这样写是比较慢的。如果遇到极端情况,比如一共100000种情况,答案是第100000个,那么前面的99999次枚举就完全是在做无用功。

稍微分析一下我们可以发现,这种写法之所以慢就是因为做了很多无用功,如果能减少做无用功的次数,就能明显提速。

于是乎,就有了二分答案这种东西。

二分答案,简单来说就是利用了二分的思想来枚举答案。比如我们先check1000,发现1000是合法的,那么这个问题的解一定不小于1000;然后,如果我们又check2000,发现2000也是合法的,那么接下来就只会往2000以上枚举,这样就省下了枚举1000~2000的时间。

代码就成了这样:

int l = 1, r = n, ans;
while (l <= r) {
    int mid = (l + r) >> 1;
    if (check(mid)) l = mid + 1, ans = mid;
    else r = mid - 1;
}
printf("%d", ans);

有人就会问了,这个check函数怎么写呢?这就要看题目情况和你的经验了。所以,得多刷刷题,积累经验。

于是乎,本蒟蒻决定放几个例题,都比较典型。

T1:【noip2015】跳石头T2:数列分段“Section II”

T3:砍树

暂时先加这三个,以后还有会继续加进来。

相关标签: 二分答案