二分例题两道 POJ1064 POJ2456

August 4, 2014 | 20:32

POJ1064

N条绳子, 长度分别Li, 切出K条长度相等的, 每条最长多长?

令C(x)代表是否可以得到K条长度为x的绳子.
对x的取值二分查找, 找到满足条件的最大的x即可.
由于是double二分, 有两种控制精度的写法

方法一:

方法二:

 

POJ 2456

 给出N个数字, 从中挑选M个, 使得挑选出来的数字之间的差的最小值最大化.

C(x)表示可以挑出M个数字使得最小差不小于x
然后对x进行二分查找就可以了.

( 转载请注明: Jecvay Notes )

说几句