剪绳子

题目 剪绳子

思路分析

令这M根绳子最长的长度为x

又因为每根绳子是独立的（不可拼接只可裁剪）

那么就应该会有 L1/x+L2/x+……+L3/x=M

（第i根绳子可以裁出Li/x根长度为x的绳子 进行一个计数cnt 最后会有M根）

现在就是要想办法找到这个x是多少

显然满足二段性 可以用二分

在公式中只有一个变量x cnt是因变量

从cnt开始分析

如果cnt≥M 就说明以当前长度裁的话 我可以分出更多段 也就是说当前并不是最大长度 边界应该是在右边 或者刚好取到的情况 找到了边界 即当前位置在x的左边或刚好取到x

如果cnt<M 说明以当前长度裁的话 我分不出M段 即裁大了 当前位置在x右边

显然就可以二分去找x 不断去用mid计算出cnt 将cnt去与M比较

若≥M 则l=mid

若<M 则r=mid

因为长度可能是小数 所以为浮点数二分问题 不存在什么有减必有加的问题

代码实现

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'

const int N=100010;
int n,m;
double L[N];

bool check(double mid){
    int cnt=0;
    for(int i=0;i<n;i++)    cnt+=L[i]/mid;
    return cnt>=m;
}

int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=0;i<n;i++)    cin>>L[i];

    double l=0,r=1e9;
    while(r-l>1e-4){
        double mid=(l+r)/2;
        if(check(mid))    l=mid;
        else    r=mid;
    }
    printf("%.2lf\n",r);
    return 0;
}

同类题型

视频讲解

⬅️ 分配给商店的最多商品的最小值 🏠 00-刷题理模型 ➡️ 卡牌