首页 > 代码库 > poj 1064 Cable master ,二分 精度!!!
poj 1064 Cable master ,二分 精度!!!
给出n根绳子,求把它们分割成K条等长的绳子的最大长度是多少?
二分
用 for(int i=0; i<100; ++i) 取代 while(r-l>eps)
循环100次精度能达到1e-30,基本上能一般题目的精度要求。
而 浮点数二分区间的话easy产生精度缺失导致死循环。
#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; }
poj 1064 Cable master ,二分 精度!!!
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。