二分例题两道 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进行二分查找就可以了.