首页 > 代码库 > poj 1064 Cable master ,二分 精度!!!

poj 1064 Cable master ,二分 精度!!!

给出n根绳子,求把它们切割成K条等长的绳子的最大长度是多少?


二分

用 for(int i=0; i<100; ++i) 代替   while(r-l>eps) 

循环100次精度能达到1e-30,基本上能一般题目的精度要求。

而 浮点数二分区间的话容易产生精度缺失导致死循环。



#include<cstdio>

double L[10000 + 10];
int n, k;

int ok(double x) {
    int cnt = 0;
    for(int i=0; i<n; ++i) {
        cnt += L[i]*1.0/x;
    }
    return cnt>=k;
}
int main() {
    while(~scanf("%d%d", &n, &k)) {
        double  Max = 0;
        for(int i=0; i<n; ++i) {
            scanf("%lf", &L[i]);
            if(Max<L[i]) Max = L[i];
        }
        double l = 0, r = Max;
        for(int i=0; i<100; ++i) {
            double mid =(l+r)/2;
            if( ok(mid) ) l = mid;
            else r = mid;
        }
        printf("%.2f\n", int(l*100)/100.0);
    }
    return 0;
}