Codeforces Round #403 (Div. 2) B. The Meeting Place Cannot Be Changed 三分

My Solution

题意：n个人每个人在xi位置且运行速度为vi，问他们相聚在一点的最短时间。

三分

打那次cf 的时候，三分还没有学，没办法。

这里直接对[minx, maxx]的范围内进行三分即可，

然后eps最开始的时候取了1e-12，后来TLE了，确实好像数据溢出了，double大概只能存十五六位有效数字。

所以改成1e-6，就过来，这里给出的   一是为了提醒eps的取值，

然后可以算一下，用1e-6时，计算出的答案误差确实最大为1e-6，刚好可以满足<=1e-6的误差要求，所以可以放心使用。

复杂度 略大于 O(nlogn)

#include 
#include 
#include 
#include 
using namespace std;
typedef long long LL;
const int MAXN = 1e6 + 8;
const double EPS = 1e-6;

int n, x[MAXN], v[MAXN];
inline double getsum(double mid)
{
    double res = 0;
    for(int i = 0; i < n; i++){ res = max(res, fabs(mid - x[i]) / v[i]); } return res; } int main() { #ifdef LOCAL freopen("b.txt", "r", stdin); //freopen("b.out", "w", stdout); int T = 4; while(T--){ #endif // LOCAL ios::sync_with_stdio(false); cin.tie(0); int i; double l = 1e9 + 8, r = 0, ll, rr, ans = 0, ans1, ans2; cin >> n;
    for(i = 0; i < n; i++){ cin >> x[i];
        l = min(l, (double)x[i]);
        r = max(r, (double)x[i]);
    }
    for(i = 0; i < n; i++) cin >> v[i];
    ans = min(getsum(l), getsum(r)); //答案一般不会取到边界，但有时候可能可以
    while(l + EPS < r){ ll = l + (r - l) / 3; rr = r - (r - l) / 3; ans1 = getsum(ll); ans2 = getsum(rr); if(ans1 > ans2){
            l = ll;
        }
        else r = rr;
        ans = min(ans, min(ans1, ans2));
    }
    cout << fixed << setprecision(12) << ans << endl;


    #ifdef LOCAL
    cout << endl;
    }
    #endif // LOCAL
    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx