二分可以简单分为 二分查找 和 二分算法,二分查找可能很多人都听过,今天想来讲讲二分答案
如果答案具有单调性且有范围,那么就可以二分枚举答案,在答案合法的条件下不断逼近最优(如最大值最小或最小值最大),最后一个合法的答案就是最优解,这便是二分答案
注解:left表示最小可能的值,right表示最大可能的值
while(left<=right)
{mid=(left+right)/2;if(check(mid)){ans=mid;left=mid+1;}else right=mid-1;
}
网上有其他很多不同的版本,比如left right、left都是double型, 二分答案的关键还是在于根据题目编写check函数,另外需要确定好left和right的实际范围 P2678 [NOIP2015 提高组] 跳石头 [P1182]数列分段 Section II [P1873 EKO / 砍树] [P1577 切绳子]实数域上的二分(板子):
while(right-left>eps){mid=(left+right)/2;if(check(mid))left=mid;elseright=mid;
}eps
为精度,一般需要保留k位小数时,esp
应取10^−(k+2)巩固练习题