Acwing 680.剪绳子

题目链接：

Acwing 680.剪绳子

解题步骤：

算法：二分

通过二分，在绳子的范围内，找出符合要求的绳子长度。

二分是通过折半查找的方式最终找到需要的结果。所以每次这种都将折中后的长度mid进行判断。

对每条绳子进行判断，看能剪出几条mid长度的绳子，累加如果超过或等于需要的绳子数量即满足要求。

二分开始的状态：l = 0; r = 100000;mid = (l+r)/2;

代码：

#include<iostream>
#include<algorithm>

using namespace std;

const int N = 100010;
int q[N];
int n,m;

//判断是否满足要求
bool check(double mid)
{
    int res = 0;
    for(int i = 0; i < n; i ++)
    {
        res += q[i] / mid;
        if(res >= m)return true;
    }
    return false;
}

int main()
{
    cin>>n>>m;

    for(int i = 0; i < n; i ++)cin>>q[i];

    double l,r,mid;
    l = 0, r = 1e9;

    // 二分查找符合条件的值
    while(r - l >= 1e-3)
    {
        mid = (l + r) / 2;
        // 如果当前值过小就取大的那部分，否则取小的那部分
        if(check(mid)) l = mid;
        else r = mid;
    }
    printf("%.2f\n",l);

    return 0;
}