洛谷链接: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;
}