poj 1064 Cable master 二分答案

缘起

日常浪费生命 poj 1064 Cable master

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
N条绳子, 长度分别为Li米(1<=Li<=100000, Li是小数,而且精确到小数点第二位). 如果要从它们中切割出K条
长度一样的绳子的话，这K条绳子每条长度至多是多少? 答案保留小数点第二位.

【输入】
第一行是N和K
1 <= N <= 10000
1 <= K <= 10000
然后是N条绳子的长度Li

【输出】
结果

【样例输入】
4 11
8.02
7.43
4.57
5.39

【样例输出】
2.00

【限制】
1s

显然是二分答案啊（因为答案具备单调性）~ 没什么好说的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
//#include "stdafx.h"

#include <stdio.h>
//#define LOCAL
#define eps 1e-6

int n,k, l[10005],max_;
double _max; // 最长

bool ck(int x) // 每条绳子按照x厘米进行切割成段
{
	int tot = 0;
	for (int i = 0; i<n;i++)
	{
		tot+=l[i]/x;
		if (tot>=k)
		{
			return true;
		}
	}
	return false;
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
//	freopen("d:\\my.out", "w", stdout);
#endif
	scanf("%d%d", &n, &k);
	for (int i = 0; i<n;i++)
	{
		double ll;
		scanf("%lf", &ll);
		if (_max+eps<ll)
		{
			_max = ll;
		}
		l[i] = (int)((ll+eps)*100); // 防止损失精度
	}
	if (k==1) // 如果只要求一段儿的话, 取最长的就行
	{
		printf("%.2lf\n",_max);
		return 0;
	}
	max_ = (int)((_max+eps)*100);
	int lo = 1, hi = max_, mid, ans=-1; // lo从1开始, 如果从0开始的话, 会RE
	while(lo<=hi) // 二分答案
	{
		mid = (lo+hi)>>1;
		if(ck(mid))
		{
			ans = mid;
			lo = mid+1;
		}
		else
		{
			hi = mid-1;
		}
	}
	if (~ans)
	{
		printf("%.2lf\n", 1.0*ans/100+eps);
	}
	else
	{
		puts("0.00");
	}
	return 0;
}

ac情况

Status Accepted
Time 110ms
Memory 152kB
Length 924
Lang C++
Submitted 2019-09-01 14:55:33
Shared
RemoteRunId 20823351