洛谷P1577 切绳子题解

题目描述

有N条绳子，它们的长度分别为Li。如果从它们中切割出K条长度相同的

绳子，这K条绳子每条最长能有多长？答案保留到小数点后2位(直接舍掉2为后的小数)。

输入输出格式

输入格式：

第一行两个整数N和K，接下来N行，描述了每条绳子的长度Li。

输出格式：

切割后每条绳子的最大长度。

输入输出样例

输入样例#1：

输出样例#1：

2.00

说明

对于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 }

47分代码

 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 }

85分代码

 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 }