ACWing 680.剪绳子 题解

本人水平有限，如有指点，欢迎各位点评。

二分 寻找边界问题 折半查找的O(logn)快速

 注：浮点数二分 注意处理double数与除数之间的相除问题，有时类型转换上会出问题。  

#include <bits/stdc++.h>

using namespace std;

int n,m,a[100010];
bool check(double mid)
{
    int cnt = 0;
    for(int i = 0;i < n;i++)
        cnt += a[i] / mid; // 每段绳子能裁剪出mid长度的总段数
    return cnt >= m;//个人认为 比较常用的写法 省去过多的if判断
}
int main()
{
    cin >> n >> m;
    int maxv = -1e9;
    for(int i = 0;i < n;i++) 
        cin >> a[i],maxv = max(a[i],maxv);// 更新出最大数 也可不更新直接写为 r = 1e9
    
    double l = 0,r = maxv,mid;
    while(r - l > 1e-4)  // 浮点数二分模板  此处精度一般比要求多精确2位即可
    {
        mid = (l + r) / 2;
        if(check(mid)) l = mid;//能裁剪出则更新左边为mid 即存在于 大于等于mid 到 r 这一段
        else r = mid;
    }
    printf("%.2f",l);
    return 0;
}

点赞随意  欢迎评论

持续充电中，一步接一步。