Day6 acwing打卡 680.剪绳子

有N根绳子，第i根绳子长度为LiLi，现在需要M根等长的绳子，你可以对N根绳子进行任意裁剪（不能拼接），请你帮忙计算出这M根绳子最长的长度是多少。

输入格式

第一行包含2个正整数N、M，表示原始绳子的数量和需求绳子的数量。

第二行包含N个整数，其中第 i 个整数LiLi表示第 i 根绳子的长度。

输出格式

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

数据范围

1≤N,M≤1000001≤N,M≤100000,
0<Li<1090<Li<109

输入样例：

3 4
3 5 4

输出样例：

2.50

样例解释

第一根和第三根分别裁剪出一根2.50长度的绳子，第二根剪成2根2.50长度的绳子，刚好4根。

利用二分思想来做这个题，对于为什么r - l > 1e-3？ 是因为浮点数二分模板的规范是这个数，所以我们只要记住即可。

#include<iostream>
using namespace std;

int N,M;
int a[100100];

bool cut(double x){
    
    int  sum = 0;
    for(int i = 0; i < N; i++){
        sum += a[i] / x;
            if (sum >= M)
        return true;
    }
    
    return false;
}

int main(){
    
    cin >> N >> M;
    
    for(int i = 0; i < N; i++)
        cin >> a[i];
    
    double r = 1e9, l = 0;

    while(r - l > 1e-3){
        double mid = l + (r - l) / 2;
        if(cut(mid)) 
            l = mid;
        else
            r = mid;
    }
    
    printf("%.2f",l);
    
    return 0;
}