浅谈二分答案
程序员文章站
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:砍树
暂时先加这三个,以后还有会继续加进来。
上一篇: 顺序查找和二分查找