Cable Master 实数的二分 hoj
/*这道题细节的地方有比较多。一个是将浮点数转化为整数来进行二分。貌似用浮点数进行二分的话精度问题会使人异常纠结。还有一个就是要注意出书不能是0.因此要加一个判断。*/#include <iostream>#include <stdio.h>#include <cstring>using namespace std;int c[10005];int n,k;bool count(int t){ int sum=0; if(t==0) return false; else { for(int i=0; i<n; i++) sum+=c[i]/t; if(sum>=k) return true; else return false; }}int main(){ char a[100]; while(scanf("%d%d",&n,&k)==2) { for(int i=0; i<n; i++) { scanf("%s",a); int x,y; sscanf(a,"%d.%d",&x,&y); c[i]=x*100+y; } int low=1,high=10000001,res=-1,mid=0; while(low<=high) { mid=(high+low)/2; if(count(mid)) { res=mid; low=mid+1; } else high=mid-1; } if(res<1) printf("0.00\n"); else printf("%.2lf\n",double(res/100.0)); } return 0;}