Codeforces Round #403 The Meeting Place Cannot Be Changed(二分，三分)

题意： 在x坐标轴上，给出n个人的横坐标的位置和每个人行走的速度，问n个人在某个点集合最短要用的时间。

题解：

方法一：由于时间越大，大到一定程度一定能全部人集合，那么二分时间。至于如何判断时间是否符合，那个时间得到每个人能走的范围，求范围是否有交集即可。

方法二：由于时间随 x 的变化函数是凹型函数，那么可以三分 x 位置。

#include <iostream>#include <cstdio>#include <cmath>#include <cstring>#include <map>#include <vector>#include <algorithm>using namespace std;const int INF = 0x3f3f3f3f;const int N = 60010;const double esp = 1e-6;struct asd{    double x,v;}a[N];int n;bool slove(double t){    double l = a[0].x - t*a[0].v;    double r = a[0].x + t*a[0].v;    for(int i = 1; i < n; i++)    {        double nextl = a[i].x - t*a[i].v;        double nextr = a[i].x + t*a[i].v;        if(nextl >= l && nextl <= r && nextr >= l && nextr <= r)            l = nextl, r = nextr;        else if(nextl >= l && nextl <= r)            l = nextl;        else if(nextr >= l && nextr <= r)            r = nextr;        else if(nextl <= l && nextr >= r)            continue;        else            return false;    }    return true;}double Bsearch(double l,double r){    double mid;    while(fabs(l-r) > esp)    {        mid = l+(r-l)/2;        if(slove(mid))            r = mid;        else            l = mid;    }    return mid;}int main(){    cin >> n;    for(int i = 0; i < n; i++)        cin >> a[i].x;    for(int i = 0; i < n; i++)        cin >> a[i].v;    //slove(2.0);    double t = Bsearch(0,1000000000);    PRintf("%.12lf/n",t);    return 0;}
#include <iostream>#include <cstdio>#include <cmath>#include <cstring>#include <map>#include <vector>#include <algorithm>using namespace std;const double INF = 0x3f3f3f3f;const int N = 60010;const double esp = 1e-6;struct asd{    double x,v;}a[N];int n;double slove(double f){    double mx = 0;    for(int i = 0; i < n; i++)    {        double t = fabs(a[i].x-f)/a[i].v;        mx = max(mx,t);    }    return mx;}double sanBsearch(double l,double r){    double midl,midr;    while(fabs(l-r) > esp)    {        midl = l+(r-l)/3;        midr = r+(l-r)/3;        if(slove(midr) > slove(midl))            r = midr;        else            l = midl;    }    return slove(midr);}int main(){    cin >> n;    double mn = INF, mx = 0;    for(int i = 0; i < n; i++)    {        cin >> a[i].x;        mx = max(mx,a[i].x);        mn = min(mn,a[i].x);    }    for(int i = 0; i < n; i++)        cin >> a[i].v;    //slove(2.0);    double t = sanBsearch(mn,mx);    printf("%.12lf/n",t);    return 0;}