二分例题两道 POJ1064 POJ2456
POJ1064
N条绳子, 长度分别Li, 切出K条长度相等的, 每条最长多长?
令C(x)代表是否可以得到K条长度为x的绳子.
对x的取值二分查找, 找到满足条件的最大的x即可.
由于是double二分, 有两种控制精度的写法
方法一:
for (int i = 0; i < 100; i++) {
double mid = (lb + ub) / 2;
if (C(mid))
lb = mid;
else
ub = mid;
}
方法二:
while (ub - lb < eps) { // eps = 0.00001
double mid = (lb + ub) / 2;
if (C(mid))
lb = mid;
else
ub = mid;
}
POJ 2456
给出N个数字, 从中挑选M个, 使得挑选出来的数字之间的差的最小值最大化.
C(x)表示可以挑出M个数字使得最小差不小于x
然后对x进行二分查找就可以了.