题目

有n条绳子，第i根绳子长度分别为L[i]，现在需要k根等长的绳子，你可以对n根绳子进行任意裁剪（不能拼接）。请你计算出这m根绳子最长的长度是多少。（答案保留小数点后两位）

二分搜索最大长度x。我们令C（x）为可以得到K条长度为x的绳子，那么问题就变为了求满足条件C（x）的最大的x。在区间初始化时，只需使用充分大的数inf（大于绳子的最大长度的二倍）作为上界即可：left=0,right=inf。那么现在的问题就变为了如何高效的判断C（x）是否满足。由于长度为L的绳子最多可以切割出floor(L/x)段长度为x的绳子，因子C（x）=floor(Li/x)的总和是否不小于k，他可以在O（n）的时间内判断出来。

代码

#include <cstdio>
#include <cmath>
using namespace std;
const int M=10005;
const double inf=2000000002.0;
double L[M];
int n,k;
bool judge(double x)
{
    int num=0;
    for(int i=0;i<n;i++)
      num+=(int)(L[i]/x);
    return num>=k;
}
void solve()
{
    double left=0,right=inf;
    for(int i=0;i<100;i++) //代替while(r>l) 避免了精度问题
    { //1次循环可以把区间缩小一半，100次可以达到10^(-30)的精度
    	//printf("%lf %lf\n",left,right); 
        double mid=(left+right)/2;
        if(judge(mid)) left=mid;
        else right=mid;
    }
    printf("%.2f\n",floor(right*100)/100);
}
int main()
{
    while(scanf("%d%d",&n,&k)!=-1)
    {
        for(int i=0;i<n;i++)
          scanf("%lf",&L[i]);
        solve();
    }
    return 0;
}