切绳子

切绳子（小数二分）

有 N 条绳子，它们的长度分别为 Li 。如果从它们中切割出 K 条长度相同的绳子，这 K 条绳子每条最长能有多长？

答案保留到小数点后 2 位（直接舍掉 2 位后的小数）。

输入：

第一行两个整数 N 和 K，接下来 N 行，描述了每条绳子的长度 Li 。

输出：

切割后每条绳子的最大长度，保证答案大于零。

样例：

1
2
3
4
5
4 11
8.02
7.43
4.57
5.39
1
2.00

1.思路

①整数二分与小数二分的不同点、②保留两位小数直接舍去的两种方法

image-20211011165744051

2.代码实现

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
#include<iostream>
#include<cmath>
#include<cstdio>
using namespace std;

int n, m;
double num[10005], mmax;

int func(double x) {
    int cnt = 0;
    for (int i = 0; i < n; ++i) {
        cnt += num[i] / x;
    }
    return cnt;
}

double bs() {
    double l = 0, r = mmax;
    //当差值大于预设精度则一直求解
    while(fabs(l - r) > 0.00005) {
        double mid = (l + r) / 2;
        //根据mid值确定能够切出的绳子数量
        int s = func(mid);
        if (s >= m) {
            l = mid;
        } else {
            r = mid;
        }
    }
    return r;
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        cin >> num[i];
        mmax = max(mmax, num[i]);
    }
    double ans = bs();
    //处理输出结果：直接舍掉2位后的小数
    double t1 = (int)(ans * 100) / 100.0;
    printf("%.2f\n", t1);
    //处理输出结果：直接舍掉2位后的小数
    printf("%.2f\n", ans - 0.005);
    return 0;
}

3.总结

小数二分与整数二分的不同点

  1. 循环条件修改：由 while(L<R/L!=R) 改为 while(abs(L-R)>0.00005) 设置精度
  2. 指针的移动修改：由 mid+1\mid-1 改为 L = mid\R = mid