AcWing 680. 剪绳子
宋标 Lv5
  2022-08-18 02:31:02 2022-08-18 02:31    

题目

有 根绳子，第 根绳子长度为 ，现在需要 根等长的绳子，你可以对 根绳子进行任意裁剪（不能拼接），请你帮忙计算出这 根绳子最长的长度是多少。

输入格式

第一行包含 个正整数 、，表示原始绳子的数量和需求绳子的数量。

第二行包含 个整数，其中第 个整数 表示第 根绳子的长度。

输出格式

输出一个数字，表示裁剪后最长的长度，保留两位小数。

数据范围

,

输入样例：

3 4
3 5 4

输出样例：

2.50

样例解释

第一根和第三根分别裁剪出一根 长度的绳子，第二根剪成 根 长度的绳子，刚好 根。

题解

小数的区间二分需掌握，保留n位小数，一般r - l区间长度为1e-n

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
#include <iostream>
#include <climits>
#define N 100010

using namespace std;

int h[N];
int n, m;

bool check(double x)
{
    int sum = 0;
    for (int i = 0; i < n; ++ i)
        sum += h[i] / x;

    return sum >= m;
}

int main()
{
    ios::sync_with_stdio(false);
    cin >> n >> m;

    int t = -INT_MAX;
    for (int i = 0; i < n; ++ i) cin >> h[i], t = max(t, h[i]);

    double l = 0, r = t;

    while (r - l > 1e-4)
    {
        double mid = (l + r) / 2;
        if (check(mid)) l = mid;
        else r = mid;
    }

    printf("%.2f", l);

    return 0;

}
 评论