网线主管

题目描述

给定 $n$ 条网线长度（米，两位小数），把它们切成 $k$ 条等长网线（剩余丢弃），求能切出的最大长度，输出两位小数；若连 $1$ 厘米都切不出则输出 0.00。

思路

长度乘 $100$ 化为厘米整数，使答案落在整数网格上。设 $f(L)=\sum_i \lfloor a_i/L \rfloor$ ， $L$ 越大段数越少，可行域是前缀，故在 $[0,\max a_i+1]$ 上开区间二分最大满足 $f(L)\ge k$ 的 $L$ ；lo=0 作为无解哨兵直接输出 0.00。

参考代码

Python 版：

python

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#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 01:23
# update_at: 2026-09-30 01:23

import sys

CM = 100  # 1 米 = 100 厘米：把"精确到厘米"的浮点长度统一放大成整数，避免浮点误差


def solve() -> None:
    data = iter(sys.stdin.buffer.read().split())
    n, k = int(next(data)), int(next(data))
    # 每条网线长度精确到厘米：乘 100 并加 0.5 四舍五入，把两位小数的浮点数安全换成厘米整数
    lens = [int(float(next(data)) * CM + 0.5) for _ in range(n)]

    # 二分答案：lo 满足"能切出 k 条"（初值 0 表示最坏切不出 1cm），hi 恒不满足
    lo, hi = 0, max(lens) + 1
    while lo + 1 < hi:
        mid = (lo + hi) // 2
        can_cut = sum(L // mid for L in lens) >= k  # 每条网线按 mid 厘米切，最多 L//mid 段
        if can_cut:
            lo = mid
        else:
            hi = mid

    # lo = 0 表示连 1 厘米都切不出 k 条，按题意输出 0.00
    print(f'{lo / CM:.2f}')


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 06:30
 * update_at: 2026-10-05 06:30
 */
#include <iostream>
#include <iomanip>
using namespace std;

typedef long long ll; // 题目数值默认 ll

const ll CM = 100; // 1 米 = 100 厘米：把精确到厘米的浮点长度放大为整数

const ll MAXN = 10005;
ll a[MAXN]; // a[i]：第 i 条网线长度对应的厘米整数
ll n, k;

// 判断按长度 L 厘米切割，能否得到不少于 k 条网线
bool check(ll L) {
    ll cnt = 0;
    for (ll i = 1; i <= n; ++i) {
        cnt += a[i] / L;
        if (cnt >= k) return true; // 提前满足可剪枝
    }
    return cnt >= k;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> k;
    ll max_a = 0;
    for (ll i = 1; i <= n; ++i) {
        double x;
        cin >> x;
        a[i] = (ll)(x * CM + 0.5); // 四舍五入，避免 8.02 * 100 = 801.99... 的浮点误差
        if (a[i] > max_a) max_a = a[i];
    }

    // 二分最大可行长度（厘米整数）
    // lo 始终可行：初值 0 表示“切不出 1 厘米”的哨兵，对应题面无解输出 0.00
    // hi 始终不可行：max_a + 1 比最长网线还长，必然一段都切不出
    ll lo = 0, hi = max_a + 1;
    while (lo + 1 < hi) {
        ll mid = (lo + hi) / 2;
        if (check(mid)) lo = mid;
        else hi = mid;
    }

    cout << fixed << setprecision(2) << (double)lo / CM << "\n";
    return 0;
}

目录

题目描述

思路

参考代码