题解：B4196 [2023 海淀区小学组] 赛车游戏

Sliarae · 2025-03-03 23:03:59 · 题解

首先预处理 s_i 表示正着从 0 走到 a_i 的最小代价，p_i 表示倒着从 l 走到 a_i 的最小代价。

钦定两个人最终在第 i 到第 i + 1 个加速带之间相遇。那么前面的人会花费 s_i 的时间，后面的人会花费 t_{i + 1} 的时间。中间还有 d = a_{i + 1} - a_i 的距离要两个人一起走。

此时考虑让两个人中用时小的一个先走，如果他用这个时间差将 d 的路程走完了说明不合法。否则这时两个人用时相同，此时他们的速度之和可以看作 n + 2，在将 \frac{d}{n + 2} 加到答案中即可。

时间复杂度 O(n)。

#include <iostream>
#include <iomanip>

using namespace std;

const int kN = 1e5 + 5;
const double Inf = 1e9;

int n;
int a[kN];
double p[kN], s[kN];

void Solve () {
    cin >> n >> a[n + 1];
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    p[0] = 0; 
    for (int i = 1; i <= n; ++i) 
        p[i] = p[i - 1] + (a[i] - a[i - 1]) * 1.0 / i;
    s[n + 1] = 0; 
    for (int i = n; i; --i)
        s[i] = s[i + 1] + (a[i + 1] - a[i]) * 1.0 / (n - i + 1);
    double ans = Inf;
    for (int i = 0; i <= n; ++i) {
        double d = a[i + 1] - a[i];
        double x = p[i], y = s[i + 1];
        if (x < y) {
            d -= (y - x) * (i + 1);
            x = y; 
        }
        else {
            d -= (x - y) * (n - i + 1);
            y = x;
        }
        if (d > 0)
            x += d / (n + 2);
        ans = min(ans, x);
    }
    cout << fixed << setprecision(12) << ans << '\n';
}

int main () {
    cin.tie(0)->sync_with_stdio(0);
    int T;
    cin >> T;
    while (T--) Solve();
    return 0; 
}