首页 > 其他 > 详细

HDU 1551 Cable master

时间:2014-02-09 16:25:21      阅读:387      评论:0      收藏:0      [点我收藏+]

题解:很显然的二分检索,在算法艺术上看过原题,不过这里要注意精度:

bubuko.com,布布扣
#include <cstdio>  
int n,m;  

double a[10001];  
bool test(double x){  
    int num=0,i;  
    for(i=1;i<=n;i++)num+=int(a[i]/x);  
    if(num>=m){  
        return true;  
    }else{  
        return false;  
    }  
}  
  
int main()
{  
    while(scanf("%d%d",&n,&m),n||m){  
            int i ;  
            double sum=0;  
            for(i=1; i<=n; ++i){  
            scanf("%lf",&a[i]);  
            sum+=a[i];  
        }  
        double max=sum/m,l=0,r=max;  
        while(r-l>1e-10){  
            double mid = (l+r)/2;  
            if(test(mid)){  
                l=mid+1e-11;  
            }else{  
                r=mid-1e-11;  
            }  
        }  
        printf("%.2lf\n",(l+r)/2);  
    }  
}  
bubuko.com,布布扣

HDU 1551 Cable master

原文:http://www.cnblogs.com/forever97/p/3541209.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!