洛谷P1577 切绳子题解
洛谷P1577 切绳子题解
题目描述
有N条绳子，它们的长度分别为Li。如果从它们中切割出K条长度相同的
绳子，这K条绳子每条最长能有多长？答案保留到小数点后2位(直接舍掉2为后的小数)。
输入输出格式
输入格式：
第一行两个整数N和K，接下来N行，描述了每条绳子的长度Li。
输出格式：
切割后每条绳子的最大长度。
输入输出样例
说明
对于100%的数据 0<Li<=100000.00 0<n<=10000 0<k<=10000
解析
本来以为是一个浮点型二分查找的题目,于是很开心的做,分数一直不一样,直到发现是一道卡精度的题目.处理这种题目一般是先乘一个大数,最后再去除以这个大数,来确保误差很小.另一个就是审题,题目中明确说是直接舍掉小数点后两位的数字,那么就按照题目,而不是四舍五入.
1 #include <cstdio> 2 #include <iostream> 3 #include <cmath> 4 #include <algorithm> 5 #define D double 6 #define E 1e-5 7 #define Max 10005 8 D l,r,a[Max]; 9 const D eps=E; 10 int n,k; 11 bool check(D x) 12 { 13 int ans=0; 14 for(int i = 1 ; i <= n ; ++ i) 15 ans += (int)a[i] / x; 16 if(ans >= k) return true; 17 else return false; 18 } 19 int main() 20 { 21 scanf("%d%d",&n,&k); 22 for(int i = 1 ; i <= n ; ++ i) scanf("%lf",&a[i]); 23 l=0,r=100000.0; 24 while(r-l > eps) { 25 D mid=(l+r) / 2; 26 if(check(mid)) l=mid; 27 else r=mid; 28 } 29 printf("%.2lf",l); 30 return 0; 31 }
1 #include <cstdio> 2 #include <iostream> 3 #include <cmath> 4 #include <algorithm> 5 #define D double 6 #define E 1e-4 7 #define Max 10005 8 D l,r,a[Max]; 9 const D eps=E; 10 int n,k; 11 bool check(D x) 12 { 13 int ans=0; 14 for(int i = 1 ; i <= n ; ++ i) 15 ans += (int)a[i] / x; 16 if(ans >= k) return true; 17 else return false; 18 } 19 int main() 20 { 21 scanf("%d%d",&n,&k); 22 for(int i = 1 ; i <= n ; ++ i) scanf("%lf",&a[i]),a[i]*=100; 23 l=0,r=100000000.0; 24 while(r-l > eps) { 25 D mid=(l+r) / 2; 26 if(check(mid)) l=mid; 27 else r=mid; 28 } 29 printf("%.2lf",l / 100); 30 return 0; 31 }
1 #include <cstdio> 2 #include <iostream> 3 #include <cmath> 4 #include <algorithm> 5 #define D double 6 #define E 1e-4 7 #define Max 10005 8 D l,r,a[Max]; 9 const D eps=E; 10 int n,k; 11 bool check(D x) 12 { 13 int ans=0; 14 for(int i = 1 ; i <= n ; ++ i) 15 ans += (int)a[i] / x; 16 if(ans >= k) return true; 17 else return false; 18 } 19 int main() 20 { 21 scanf("%d%d",&n,&k); 22 for(int i = 1 ; i <= n ; ++ i) scanf("%lf",&a[i]),a[i]*=100; 23 l=0,r=100000000.0; 24 while(r-l > eps) { 25 D mid=(l+r) / 2; 26 if(check(mid)) l=mid; 27 else r=mid; 28 } 29 l /= 100 ; 30 if(l-0.0049 > 0) l -= 0.0049; 31 printf("%.2lf",l); 32 return 0; 33 }
大疆公司氛围 166人发布
