题目传送门:洛谷P1577 切绳子

实数二分,精度会缺失(如果直接用double二分,最后%.2lf输出的时候会自动向上取整,可能改变了答案),解决办法是先把每根绳子长度a[i]乘以100化为整数,再按整数的方法二分,最后输出答案时再除以100即可。

注意在二分过程中要特判m=0的情况(否则在judge函数中会除以0导致RE),m=0时直接break退出二分循环,记下答案ans=0。

AC代码:

#include <bits/stdc++.h>
using namespace std;
const int N=1e4+10;
double x,ans;
int n,k,l,r,m,a[N];
bool judge(int m)
{
    int s=0;
    for(int i=1;i<=n;i++)
        s=s+a[i]/m;//m!=0才可使用judge函数判断
    return s>=k;//有等于号
}
int main()
{
    ios::sync_with_stdio(false);
    while(cin>>n>>k)//分成k段
    {
        for(int i=1;i<=n;i++)
        {
            cin>>x;
            a[i]=(int)(x*100);
        }
        l=0,r=1e7;
        while(l<=r)
        {
            m=l+(r-l)/2;
            if(m==0){ans=0;break;}
            //n=1 k=10000 a[1]=1.00时,二分过程中会出现m=0的情况,在judge函数中会除以0导致RE
            //要防止RE,则特判二分过程中m=0直接break,退出二分,记下答案ans=0
            if(judge(m))ans=1.0*m,l=m+1;//满足if(judge(m)),记下ans
            else r=m-1;
        }
        printf("%.2lf\n",ans/100.0);
    }
    return 0;
}