POJ 1064 Cable master （二分）

链接:http://poj.org/problem?id=1064

题目：有n条绳子，长度分别为L[i]。如果从他们中切割出k条长度相同的绳子的话，这k条绳子每条最长能有多长？（答案保留小数点后两位，规定1单位长度的绳子最多可以切割成100份）。

分析：二分搜索最大长度x。我们令C（x）为可以得到K条长度为x的绳子，那么问题就变为了求满足条件C（x）的最大的x。在区间初始化时，设置maxL为所有绳子中的最大值，其作为上界：left=0,right=maxL。那么现在的问题就变为了如何高效的判断C（x）是否满足。由于长度为L的绳子最多可以切割出floor(L/x)段长度为x的绳子，因子C（x）=floor(Li/x)的总和是否不小于k，他可以在O（n）的时间内判断出来。总体时间复杂度n*logn

注意浮点数精度的问题，因为精度的问题wa了无数次

AC代码：

 1 #include<iostream>
 2 #include<cmath>
 3 #include<algorithm>
 4 #include<cstdio>
 5 #include<vector>
 6 #include<queue>
 7 #include<cstring>
 8 #include<set>
 9 #define inf 0x3f3f3f3f
10 using namespace std;
11 typedef long long LL;
12 double L[100005];
13 int n,k;
14 bool check(double cur){
15     int sum = 0;
16     for(int i = 0;i<n;i++){
17         sum+=(int)(L[i]/cur);
18     }
19     if(sum>=k) return true;
20     else return false;
21 }
22 int main(){
23     while(~scanf("%d%d",&n,&k)){
24         double maxL = 0;
25         for(int i = 0;i<n;i++) {
26             cin>>L[i];
27             maxL = max(maxL,L[i]);
28         }
29         double l = 0,r = maxL;
30         for(int i = 0;i<100;i++){//循环100次一般可以把精度精确到1e-30 
31             double mid = (l+r)/2;
32             if(check(mid)) l = mid;
33             else r = mid;
34         }
35         printf("%.2f\n",floor(l*100)/100);//乘100向下取整，去掉2位小数后面的数字
36     }
37     return 0;
38 }