【二分查找】剪绳子

题目

680. 剪绳子 - AcWing题库

---

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

输入格式

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

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

输出格式

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

数据范围

$1 \le N,M \le 100000$ ,
$0 < L_i < 10^9$

输入样例：

3 4
3 5 4

输出样例：

2.50

样例解释

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

解题

方法一：二分查找

思路

最大化最小值，经典二分题，模板二(条件满足时尽量往大了取)+浮点数二分。

注意：

• 二分的初始左边界取 $0$，右边界取原绳子中的最长值。
• eps 一般取题目要求精度小 $1 \sim 2$ 位。

代码

#include <iostream>

using namespace std;

const int N = 1e5 + 10;
const double eps = 1e-4;
int n, M, a[N];

bool check(double m) {
    int cnt = 0;
    for (int i = 0; i < n; ++i) {
        cnt += (int) (a[i] / m);
        if (cnt >= M) return true;
    }
    return cnt >= M;
}

int main() {
    scanf("%d%d", &n, &M);
    double l = 0.0, r = 0.0;
    for (int i = 0; i < n; ++i) {
        int x;
        scanf("%d", &x);
        r = max(r, x * 1.0);
        a[i] = x;
    }
    while (r - l > eps) {
        double m = (l + r) / 2;
        if (check(m)) l = m;
        else r = m;
    }
    printf("%.2lf\n", l);
    
    return 0;
}