二分搜索的变形题

poj1064

有n个绳子，它们的长度分别是Li,如果从它们中切割出K条长度相同的绳子的话，这K条绳子每条最长能有多长？保留到小数点后2位。

1<=N<=10000
1<=K<=10000
1<=Li<=100000

AC

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<iostream>
#include <math.h>
using namespace std;

double L[10000+5];

bool f(double x,int n,int k)
{
    int num=0;
    for(int i=0;i<n;i++)
    {
        num+=(int)(L[i]/x);
    }
    return num>=k;
}
int main()
{
    int n,k;
    double l=0,r=100000;    //r的取值是限制条件的右边界。 书中说INF，含义为下确界，并无实际数值意义
    cin>>n>>k;
    for(int i=0;i<n;i++)
    {
        cin>>L[i];
    }
    for(int i=0;i<100;i++)
    {
        double mid=(l+r)/2;
        if(f(mid,n,k)) l=mid;
        else r=mid;
    }
    printf("%.2f\n",floor(r*100)/100);   //floor(x)返回的是小于或等于x的最大整数
    return 0;
}