二分法，三分法的应用

在了解了关于二分法，三分法的相关原理之后，需要进一步熟练运用，下面两道题：

二分法应用：
HDU Cable master：
http://acm.hdu.edu.cn/game/entry/problem/show.php?chapterid=4&sectionid=1&problemid=10
题意：n个木棒，分成m个大小相等的小木棒，问分割后最大的长度是多少？
如：2.00 ， 3.00 ， 4.00长度的三根木棒，分成2个，最大的应该是3，而不是4。
开始二分：由于每根的大小必定大于1，那么长度应该在1和最长的木棒长度之间，由此二分，总的木棒可以分成长度为mid的木棒数量大于m，那么，可以使mid增加，即left=mid+1，否则使mid减小，right=mid-1，直到left=mid。
代码如下：

#include<iostream>
using namespace std;

int main()
{
    double temp,eps=1e-7;
    int i,sum,max,low,high,mid,ans,n,k,s[10001];
    while(cin>>n>>k && (n||k))
    {
        sum=max=0;
        for(i=0;i<n;i++)
        {
            cin>>temp;
            s[i]=(int)((temp+eps)*100);
            if(max<s[i])
                max=s[i];
        }

        ans=0;
        low=1;
        high=max;
        while(high>=low)
        {
            sum=0;
            mid=(low+high)/2;
            for(i=0;i<n;i++)
                sum+=s[i]/mid;
            if(sum>=k)
            {
                low=mid+1;
                if(ans<mid)
                    ans=mid;
            }
            else
                high=mid-1;
        }
        printf("%.2lf\n",ans*0.01);
    }
}

三分法应用：
HDU Line belt
http://acm.hdu.edu.cn/game/entry/problem/show.php?chapterid=4&sectionid=1&problemid=9
题意：过河，两个平行线AB，CD，想要从A到达D，已知在AB，CD和其他地方的速度，求解所用的最短时间。
三分思维：三分法可以得到两段的最短时间，如：

假设已知拐点a，c，从ac中选择一个b点，使得在ab，bc上用的总时间为最少，那么，可以解答出相关的b点，而a点是不确定的，可以在三分算法中使用三分算法，规划成两个以上的结构，具体实现看代码：

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#define eps 1e-8
using namespace std;
int sgn(double n){
    if(fabs(n)<eps)return 0;
    else if(n<0)return -1;
    return 1;
}
struct point{
    double x,y;
}A,B,C,D;
double p,q,r;
double dist(point p1,point p2){
    return sqrt((p2.x-p1.x)*(p2.x-p1.x)+(p2.y-p1.y)*(p2.y-p1.y));
}
double Three2(point a){
    point left=C,right=D;
    point mid,mmid;
    double t1,t2;
    int size=100;
    while(size--){
        mid.x=(left.x+right.x)/2.0;
        mid.y=(left.y+right.y)/2.0;
        mmid.x=(mid.x+right.x)/2.0;
        mmid.y=(mid.y+right.y)/2.0;
        t1=dist(a,mid)/r+dist(mid,D)/q;
        t2=dist(a,mmid)/r+dist(mmid,D)/q;
        if(t1>t2)
            left=mid;
        else 
            right=mmid;
    }
    return t1;
}
double Three1(){
    point left=A,right=B;
    point mid,mmid;
    double t1,t2;
    int size=100;
    while(size--){
        mid.x=(left.x+right.x)/2.0;
        mid.y=(left.y+right.y)/2.0;
        mmid.x=(mid.x+right.x)/2.0;
        mmid.y=(mid.y+right.y)/2.0;
        t1=dist(A,mid)/p+Three2(mid);
        t2=dist(A,mmid)/p+Three2(mmid);
        if(t1>t2)
            left=mid;
        else
            right=mmid;
    }
    return t1;
} 
int main()
{
    int t,i,j,k;
    scanf("%d",&t);
    while(t--){
        scanf("%lf%lf%lf%lf",&A.x,&A.y,&B.x,&B.y);
        scanf("%lf%lf%lf%lf",&C.x,&C.y,&D.x,&D.y);
        scanf("%lf%lf%lf",&p,&q,&r);
        printf("%.2lf\n",Three1());
    }
    return 0;
}