7.10二分

快乐的暑假生活从现在开始了，我也开始了我最后的OIer之旅的冲刺阶段。那么我觉得我有必要每天写一篇博客来记录一下当天发生的一些事情和所学的一些东西。

今天我们的老师主要给我们讲了一下关于二分的一些知识点。

下面我就以两道例题简单的来总结一下所学的内容。

题目传送门：
P2678 跳石头

题意很简单，就是你知道每块石头到起点的距离，现在要你搬一些石头然后使，最小的距离最大，问你最小的距离最大是多少。

这道题其实是一道二分答案的题，我们知道答案一定就是在从0~起点到终点的距离之间，所以我们只要对这个东西进行二分就可以了，每次二分会有一个答案，对于这个我们不知道行不行的答案，我们要代入题目中实际操作一下我们到底满足这个答案需要搬走多少块石头，如果要搬走的石头太多了，说明我们实验的答案太大，所以我们就要在答案区间的左边进行二分，如果太小了我们就在答案区间的右边进行二分，其实说实在的这个东西其实很像给一个区间进行猜数游戏，我们每次对我们的答案区间进行二分，然后我们就可以很快的找到答案了。其实很像了！

相信大家脑补一下都应该知道应该怎么写了：

代码如下：

#include<bits/stdc++.h>
using namespace std;
int l,m,n;
int len[50005],dis[50005];
int minx=1000000;
int search(int mid)
{
    int cnt=0;
    for(int i=0;i<=n;++i)
    {
        int p=1;
        while(len[i+p]-len[i]<mid&&i+p<=n)
        {p++;cnt++;}
        i=i+p-1;

    }
    return cnt;
}
int main()
{
    len[0]=0;
    scanf("%d%d%d",&l,&n,&m );
    if(m==0) {printf("%d",l);exit(0);} 
    for(int i=1;i<=n;++i)
    {
        scanf("%d",&len[i]);
        if(minx>len[i]) minx=len[i];
        dis[i-1]=len[i]-len[i-1];
    }
    len[n+1]=l;
    dis[n]=len[n+1]-len[n];
    int p1,p2;
    p1=0;p2=len[n];
    int mid;
    int ans;
    while(p1<=p2)
    {
        mid=(p1+p2)/2;
        int goal=search(mid);
        if(goal<=m){p1=mid+1;ans=mid;}//!!!!
        if(goal>m){p2=mid-1;}
    }
    printf("%d",ans);
    return 0;
} 

相信大家从这道比较神奇的二分题目中应该都知道这个二分到底是怎么玩的了。

下面我们就来说一下三分法！

三分法说白了就是在二分法的基础上在分一次（不均匀三分）当然你也可以均匀三分其实效果差不多，但是还是要依具体题目来说，最好大家都是均匀三分。

为什么会存在三分法呢？

其实这个问题我一开始接触到这个方法的时候我也问了我的老师，是因为三分他可以解决一些二分不能解决的问题，不如说我们可以很明显的发现二分这个东西很多时候他二分的东西是有单调性的，只有这些东西我二分的时候以中间为标志我才能知道左边的比我大（或小）右边的比我小（或大）如果这个东西不具有单调性，那么我就不知道我取这个标志有什么意义，因为我不知道标志的左边意味着什么，标志的右边意味着什么！而三分法的出现可以帮助我们解决单峰函数求最值的类型。所以说这个方法还是很有用的，具体的用处我们用第二道例题来体现。

题目传送门： P2571 [SCOI2010]传送带

题意这里不做过多解释大家看一下。

题目大致思路如下：

其实这道题是十分的感性，我们是如何看出他是一个单峰函数的呢？

因为我们需要感性理解嘛！其实我也不知道是怎么证明的，但是这里有一个非常愚蠢的方法，就是我们假设我们已经知道了最短路径应该是怎么走的，那么我们就先固定一个点然后移动另一个点，那么我们可以感性的这么想，因为我们知道那个一定是最短的路径了，所以无论我们上移还是下移我们都可以发现这都应该不是最短的路径，所以每个传送带上的一个点都是一个单峰函数，而因为有两个传送带，所以有两个单峰函数，然后把他们嵌套起来就可以了。所以这道题其实是一道三分套三分的版题，最后提醒一句，这道题可以用不均匀三分A掉，是不是感觉节约了一些代码量啊？

代码如下：

#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std;
const double jd=0.00001;
double xa,ya,xb,yb,xc,yc,xd,yd,p,q,r;
double dis(double xe,double ye,double xf,double yf)
{
  return ((sqrt((xe-xa)*(xe-xa)+(ye-ya)*(ye-ya)))/p)+((sqrt((xf-xe)*(xf-xe)+(ye-yf)*(ye-yf)))/r)+((sqrt((xd-xf)*(xd-xf)+(yd-yf)*(yd-yf)))/q);
}
double tri(double x,double y)
{
    double p1=xc,p2=xd,p11=yc,p22=yd;double minn;
    while(fabs(p1-p2)>jd||fabs(p11-p22)>jd)
    {
        double midx=(p1+p2)/2,midy=(p11+p22)/2;
        double tmidx=(midx+p2)/2,tmidy=(p22+midy)/2;
        double ans1=dis(x,y,midx,midy),ans2=dis(x,y,tmidx,tmidy);
        if(ans1>ans2){p1=midx;p11=midy;}
        else {p2=tmidx;p22=tmidy;}
        minn=min(ans1,ans2);
    }
    return minn;
}
int main()
{
    scanf("%lf%lf%lf%lf%lf%lf%lf%lf%lf%lf%lf",&xa,&ya,&xb,&yb,&xc,&yc,&xd,&yd,&p,&q,&r);
    double p1=xa,p11=ya,p2=xb,p22=yb;
    double ans;
    while(1)
    {
        double midx=(p1+p2)/2,midy=(p11+p22)/2;
        double tmidx=(midx+p2)/2,tmidy=(midy+p22)/2;
        double ans1=tri(midx,midy),ans2=tri(tmidx,tmidy);
        if(ans1>ans2){p1=midx;p11=midy;}
        else{p2=tmidx;p22=tmidy;}
        ans=min(ans1,ans2);
        if(fabs(p1-p2)<jd&&fabs(p11-p22)<jd) break;
    }
    printf("%.2lf",ans);
    return 0;
}

By njc