poj 1064 Cable master ,二分 精度!!!
poj 二分 Master 精度
2023-09-27 14:27:04 时间
给出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 2195 Going Home
- 【POJ】2187 Beauty Contest(旋转卡壳)
- 【POJ】2947 Widget Factory(高斯消元)
- POJ 2391 Ombrophobic Bovines (Floyd + Dinic +二分)
- poj 2182 Lost Cows
- poj - 1873 - The Fortified Forest
- poj 2566 Bound Found 尺取法
- POJ 1743 Musical Theme (字符串HASH+二分)
- POJ 2417 Discrete Logging (Baby-Step Giant-Step)
- POJ 1236 Network of Schools (有向图的强连通分量)
- 状态压缩动态规划 -- 棋盘问题 POJ 1321
- poj 1011 Sticks ,剪枝神题
- POJ 3020:Antenna Placement(无向二分图的最小路径覆盖)