学步园

什么是二分？

简单点说就是折半寻找一个数

	       double l=0,r=INF;//头尾
        for(int i=0; i<100; i++)//重复循环似的范围住够小
        {
            double mid=(l+r)/2;
            if(ac(mid))//判断是否可行
            {
                l=mid;
                cout<<mid<<endl;
            }
            else {r=mid;
                cout<<mid<<endl;
            }
        }

poj 1064

#include<iostream>
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<algorithm>
using namespace std;
int n,k;
double L[10005];
bool ac(double x)
{
    double sum=0;
    for(int i=0; i<n; i++)
        sum+=(int)(L[i]/x);//只可能是整数根绳子
    return sum>=k;
}
int main()
{
    while(cin>>n>>k)
    {
        double max=0;
        for(int i=0; i<n; i++)
        {
            cin>>L[i];
            if(max<L[i])
                max = L[i];
        }

        double INF = max ;//把上界设为最大的 方便查找
        double l=0,r=INF;//头尾
        for(int i=0; i<100; i++)//重复循环似的范围住够小
        {
            double mid=(l+r)/2;
            if(ac(mid))
            {
                l=mid;
                cout<<mid<<endl;
            }
            else {r=mid;
                cout<<mid<<endl;
            }
        }
        printf("%.2lf\n",floor(r*100)/100);
    }
}

二分搜索的结束判断

在输出小数的问题中，一般都·会指定允许的误差范围或者是指点输出中小数点后面的位数。

因此在使用二分搜索是，有必须设置合理的结束条件来满足精度

1次循环可以吧区间缩写一半 100循环和缩写到1e-30的精度，一般来说没有问题。

但是区间如果取得过小，很可能造成死循环