---
title: "剪绳子"
created: 2025-11-28
tags:
  - 算法
---

# 剪绳子

## 题目 [剪绳子](https://www.acwing.com/problem/content/description/682/)

![[image-5e3127b6.png]]

## 思路分析

令这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

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

## 代码实现

```cpp
#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-刷题理模型]] ➡️ [[2-Learning/02-算法/03-刷题理模型/二分相关模型/卡牌|卡牌]]