在了解了关于二分法，三分法的相关原理之后，需要进一步熟练运用，下面两道题：
二分法应用：
HDU Cable master：
http://acm.hdu.edu.cn/game/entry/problem/show.php?chapterid=4§ionid=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§ionid=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;
}
