割绳子

TimeLimit:1000MS  MemoryLimit:10000K
64-bit integer IO format: %lld
Problem Description

已知有n条绳子,每根绳子至少1米,每条绳子都有一定的长度(单位,米),从中切割出K条长度相同的绳子,求这K条绳子每条最长能有多长?绳子的长度不能小于1厘米,如果不能满足输出 0.00,答案向下保留两位小数(比如1.799999向下保留两位后是1.79 即后面的数字全部舍去)。

Input

输入一行有两个数N,K(1<=N,K<=10000).

第二行有N个数,表示每条绳子的长度(1<=Li<=100000),每个输入都有两位小数.

输入double用%lf,输出用%f,用scanf输入.

Output

输出满足条件的绳子的最长长度(向下保留两位小数).

SampleInput
4 11
8.02
7.43
4.57
5.39
SampleOutput
2.00

思路:直接枚举判断坑定超时。二分的思路。正常二分在有序列上界,下界之间找一个数字N。这题可以理解为在绳子合理范围内找一个数值满足能切K条绳子的条件的长度。而且是最长长度,就类似于找二分上界。不懂二分的找我们寒假作业上面的博客。
绳子合理范围即初始区间是[0,n项和/k],n项和/k是理想情况不考虑绳子分段的最大长度,或者默认用一个比较大的数字开始分也可以。然后开始二分缩小区间。二分核心代码。

用time控制循环次数缩小区间。

二分的循环体内,用数组存每段绳子的长度,求每段绳子按二分暂时求的每条绳子长度分成的实际绳子的段数。求和作为二分区间判断条件。

第一个if可以理解为当求得绳子长度满足条件后,继续扩大mid求是否满足条件。知道time==0,误差范围差不多够了。