題意： 在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;}