https://www.cnblogs.com/violet-acmer/p/9793209.html
题意:
有N条绳子,长度分别为 length[1,2,3,........,N]。
如果从它们中切割出K条长度相同的绳子,这K条绳子每条最长有多长?
结果保留两位小数。
题解:
二分可能的长度。
AC代码:
精度问题:
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
1 #include<iostream> 2 #include<cstdio> 3 #include<cmath> 4 using namespace std; 5 const int maxn=1e4+50; 6 7 int N,K; 8 double length[maxn]; 9 10 bool Check(double x) 11 { 12 int total=0; 13 for(int i=1;i <= N;++i) 14 total += (int)(length[i]/x); 15 return total >= K ? true:false; 16 } 17 int main() 18 { 19 scanf("%d%d",&N,&K); 20 double maxL=0; 21 for(int i=1;i <= N;++i) 22 { 23 scanf("%lf",length+i); 24 maxL=max(maxL,length[i]); 25 } 26 //解范围为 [l,r) 27 double l=0,r=maxL+1; 28 for(int i=1;i <= 100;++i) 29 { 30 double mid=l+((r-l)/2); 31 if(Check(mid))//如果mid满足条件,则解的范围变为 [mid,r) 32 l=mid; 33 else 34 r=mid;//反之,解的范围变为[l,mid) 35 } 36 printf("%.2f\n",floor(l*100)/100);//printf()会四舍五入,而如果5入的话就不满足条件了 37 return 0; 38 }