一 问题描述

二 算法设计

1 二分搜索。初始时，l=0.00，r=inf，r 也可以被初始化为 N 条电缆的最大长度。mid=(l+r)/2，判断出切割出来电缆的长度为 mid，是否可以切割出 K 条。如果可以，则让 l = mid,增加长度搜索，否则 r=mid，减少长度搜索。

2 判断 mid 是否可行。枚举 N 条电缆，累加每条电缆可以切割出的数量，注意该数量要取整，如果数量大于或等于 K，则表示可行。

3 可以用 r-l > eps 判断循环条件，也可以在搜索较大的次数时停止，例如 100 次。结束时返回 l。

4 输出答案。要求保留两位小数。

三 代码

package com.platform.modules.alg.alglib.poj1064;

public class Poj1064 {
    private int inf = 0x3f3f3f3f;
    private static double eps = 1e-7;
    private double L[] = new double[10005];
    private int n;
    private int k;

    // 假设切割出来的绳子的长度为x，判断够不够切割
    boolean judge(double x) {
        int num = 0;
        for (int i = 0; i < n; i++)
            num += (int) (L[i] / x);
        return num >= k;
    }

    double solve() {
        double l = 0;
        double r = inf;
        while (r - l > eps) {
            double mid = (l + r) / 2;
            if (judge(mid))
                l = mid;
            else
                r = mid;
        }
        return l;
    }

    public String cal(String input) {
        String[] line = input.split("\n");
        String[] words = line[0].split(" ");
        n = Integer.parseInt(words[0]);
        k = Integer.parseInt(words[1]);
        for (int i = 0; i < n; i++) {
            L[i] = Double.parseDouble(line[i + 1]);
        }
        double ans = solve() + eps;
        return String.format("%.2f", Math.floor(ans * 100) / 100);
    }
}

四 测试