侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 551 篇文章
  • 累计创建 117 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

【二分查找】剪绳子

GabrielxD
2022-12-30 / 0 评论 / 0 点赞 / 14 阅读 / 499 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2022-12-30,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

680. 剪绳子 - AcWing题库


NN 根绳子,第 ii 根绳子长度为 LiL_i ,现在需要 MM 根等长的绳子,你可以对 NN 根绳子进行任意裁剪(不能拼接),请你帮忙计算出这 MM 根绳子最长的长度是多少。

输入格式

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

第二行包含 NN 个整数,其中第 ii 个整数 LiL_i 表示第 ii 根绳子的长度。

输出格式

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

数据范围

1N,M1000001 \le N,M \le 100000 ,
0<Li<1090 < L_i < 10^9

输入样例:

3 4
3 5 4

输出样例:

2.50

样例解释

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

解题

方法一:二分查找

思路

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

注意:

  • 二分的初始左边界取 00,右边界取原绳子中的最长值。
  • eps 一般取题目要求精度小 121 \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;
}
0

评论区