二分法截绳子

题：

N根绳子，需要M根等长的绳子，可以截取，不可以拼接

思路：
求可以截的的最长进而可以联想到二分，一般二分就是求在一个递增序列上的一个阈值。然而二分猜可能的长度，每个棒子除一下猜的长度，得到能截到的个数，然后计算总数是不是大于m，大于说明可以放大猜测的阈值，如果不够m个就往小的猜。就是这样

作者：WAzidongji
链接：https://www.nowcoder.com/discuss/163804
来源：牛客网

#include<bits/stdc++.h>
 
using namespace std;
typedef long long ll;
 
int n, m;
double a[1000010];
const double eps = 1e-4;
 
bool ok(double x)
{
    int cnt = 0;
    for(int i = 0; i < n; i++)
    {
        cnt += a[i] / x;
    }
    return cnt >= m;
}
int main()
{
    cin >> n >> m;
    for(int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    double l = 0, r = 1e9 + 77;
    while(l + eps < r)
    {
        double mid = (l + r) / 2;
        if(ok(mid)) l = mid;
        else r = mid;
    }
    printf("%.2f
",l);
    return 0;
}