洛谷链接:P1577 切绳子

看到我写这么简单的题的题解不要奇怪,因为这题很坑……XJ一大堆dalao都已经被坑害了……

题目描述

有N条绳子,它们的长度分别为Li。如果从它们中切割出K条长度相同的
绳子,这K条绳子每条最长能有多长?答案保留到小数点后2位。

输入输出格式

输入格式:

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

输出格式:

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

输入输出样例

输入样例#1:

4 11
8.02
7.43
4.57
5.39

输出样例#1:

2.00

说明

对于100%的数据 0<Li<=100000.00 0<n<=10000 0<k<=10000

题解

本来这是入门的二分题目,但是!!!会有精度问题!

题目要求我们取小数点后两位,意思是向下取,但是 printf("%.2f",ans); 这个语句自带四舍五入!如果按这样写它会自动把小数点后第三位四舍五入累加到第二位上……

所以一种处理方法是把所有数据乘以100,再按整数做,最后答案除以100按小数输出,这样可以避免精度问题。

另外一种做法就是把答案连小数点之后三位输出到一个字符数组里(我现在才知道有sprintf这种黑科技……),再直接暴力地把小数点之后第三位截掉……代码如下:

sprintf(s+1,"%.3f",ans);
s[strlen(s+1)]='\0';
printf("%s",s+1);

(我也很奇怪为什么我之前一直没注意到精度的事情……)

参考代码

贴上这题的完整代码:

#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
using namespace std;
const int maxn=10005;
int n,m;
char s[100];
double a[maxn],sum=0.0,ans=0.0;
inline bool check(double x){
    int cnt=0;
    for (int i=1;i<=n;i++) cnt+=trunc(a[i]/x);
    return cnt>=m;
}
int main(){
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++){scanf("%lf",&a[i]);sum+=a[i];}
    double L=0.0,R=sum+1.0,mid;
    while (R-L>1e-4){
        double mid=(L+R)/2.0;
        if (mid==0.0) break;
        if (check(mid)){
            ans=mid;
            L=mid;
        } else R=mid;
    }
    sprintf(s+1,"%.3f",ans);
    s[strlen(s+1)]='\0';
    printf("%s",s+1);
    return 0;
}