POJ 1064 Cable master（浮点数二分 精度处理）

POJ 1064 Cable master（浮点数二分 精度处理）

题目：

​ 给出n棵木头，现在要求将木头裁成k个长度相同的小木头，请问这k个小木头的最大长度是多少。裁出来后不支持拼接。所有长度都是小数点后两位，要求输出答案也是小数点后两位。

思路：

​ 非常简单的一个二分。但是交一发之后发现会因为精度出现四舍五入的误差。又因为题目将所有数据都限制在后两位小数，所以我们可以将二分出来的结果*100后取整再/100，就是正确的精度了。

实现：

typedef long long ll;

int n, k;
double a[100005];

bool check(double x)
{
	ll cnt = 0;
	for(int i = 1; i <= n; i ++)
		cnt += floor(a[i] / x);
	return cnt >= k;
}

int main()
{
	scanf("%d%d", &n, &k);
	for(int i = 1; i <= n; i ++)
		scanf("%lf", &a[i]);

	double l = 0, r = 1000000.0;
	for(int i = 1; i <= 100; i ++)
	{
		double mid = (l + r) / 2.0;
		if(check(mid))	l = mid;
		else 	r = mid;
	}
	printf("%.2f\n", floor(l * 100) / 100);
}