网线主管

题意

将库存网线切成至少指定数量的等长段，求能得到的最大长度，结果精确到厘米。

思路

把米转换为厘米整数，避免浮点误差。若每段长度为 length，一条网线能贡献 wire // length 段；总段数不少于需求时该长度可行。长度越短越容易可行，满足二分答案的单调性。

代码

Python代码

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19wire_count, required_count = map(int, input().split())
wires = [int(round(float(input()) * 100)) for _ in range(wire_count)]


def can_cut(length: int) -> bool:
    return sum(wire // length for wire in wires) >= required_count


low, high = 1, max(wires)
answer = 0
while low <= high:
    middle = (low + high) // 2
    if can_cut(middle):
        answer = middle
        low = middle + 1
    else:
        high = middle - 1

print(f"{answer / 100:.2f}")

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#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;

int n,k;
int a[maxn];


// len = length
int num(int len){
    int cnt = 0;
    for(int i =1;i<=n;i++){
        cnt += a[i] / len;
    }
    return cnt;
}

int mid(int l,int r) {
    return (l+r) >> 1; //这是最快的写法
}

//检查pos位置的值是否符合要求
bool check(int len){
    int cnt = num(len);
    return cnt >= k;
}

//bs_find = binary search find
int bs_find(int l,int r) {
    while( l < r) {
        int m = mid(l,r);
        if( !check(m))//不成立
            r = m;
        else //成立,抛弃左半边
            l = m+1;
    }
    return l ;
}

int main(){
    cin >> n >> k;
    for(int i =1;i<=n;i++){
        double t;
        cin >> t;
        a[i] = t *100;
    }
    // 1km = 1000m
    // 1m = 100 cm
    // 1km = 1000 * 100 cm
    int ans = bs_find(1,100*1000*100+1);
    ans--;
    cout << fixed << setprecision(2) << ans *1.0 / 100 << endl;
    return 0;
}

复杂度

时间复杂度为 $O(n \log M)$ ， $M$ 是最长网线的厘米长度；空间复杂度为 $O(n)$ 。

总结

要求固定小数精度时，先转换为最小单位整数常能让二分更可靠。

目录

题意

思路

代码

Python代码

C++代码

复杂度

总结