题解:使用二分搜索,在输出小数问题上,一般都会指定允许的误差范围或者是输出中小数点后面的位数。因此在使用二分搜索法时,有必要设置合理的结束条件来满足精度的要求。
设定循环次数作为终止条件,1次循环可以把区间的范围缩小一半,100次的循环则可以达到10^(-30)的精度范围,基本上是没有问题的,也可以把精度设置为(ub-lb)>eps这样,指定一个区间的大小。在这种情况下,如果eps取得太小了,就有可能因为浮点小数精度的原因陷入死循环。
原文链接:https://blog.csdn.net/zhouzi2018/article/details/82918701
注:这个输出真的很迷
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <string> #include <map> #include <stack> #include <vector> #include <set> #include <queue> #include<iomanip> #define endl '\n' #define _for(i,a,b) for(int i=a;i<b;i++) #define EPS 1e-10 using namespace std; const int N = 1e4+5; typedef long long ll; double Y ; double a[N]; int n,m; bool check(double x){//TOO LONG int cnt = 0; _for(i,1,n+1){ cnt+= int( a[i]/x ); } return cnt>=m; } int main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); cin>>n>>m; _for(i,1,n+1){ cin>>a[i]; } double L = 0,R = 1e6+5,t =100; while( fabs(R-L) > EPS ){ double mid = (L+R)/2; if( check(mid) ) L = mid; else R = mid; } cout<<fixed<<setprecision(2)<< floor(L*100)/100 <<endl; return 0; }
另一种解法
https://www.cnblogs.com/nyist-xsk/p/7264846.html