题解 CF1408C 【Discrete Acceleration】

· · 题解

对每个点计算左边的车到达这个点的时间，以及右边的车到达这个点的时间，然后找到两辆车相遇的位置即可。

\Theta(n)

code : 

#include <bits/stdc++.h>
#define db long double
using namespace std;
template <typename T> void read(T &x){
    static char ch; x = 0,ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) x = x * 10 + ch - '0',ch = getchar();
}
const int N = 100005;
int n,l,a[N]; db tl[N],tr[N];
inline void solve(){
    int i,p; db ans = 1e18,nt,nx,ny;
    read(n),read(l);
    a[0] = 0; for (i = 1; i <= n; ++i) read(a[i]); a[++n] = l;
    tl[0] = 0; for (i = 1; i <= n; ++i) tl[i] = tl[i-1] + (a[i] - a[i-1]) * 1.0 / i;
    tr[n] = 0; for (i = n-1; i >= 0; --i) tr[i] = tr[i+1] + (a[i+1] - a[i]) * 1.0 / (n-i); 
    for (i = 0; i < n; ++i){
        nt = max(tl[i],tr[i+1]),nx = a[i] + (nt-tl[i]) * (i+1),ny = a[i+1] - (nt-tr[i+1]) * (n-i);
        if (nx <= ny) ans = min(ans,nt + (ny-nx) / (n+1));
    }
    cout << fixed << setprecision(20) << ans << '\n';
}
int main(){ int T; read(T); while (T--) solve(); return 0; }