2019 Multi-University Training Contest 1 - Vacation

Bertha 。 2021-11-08 17:34 125阅读 0赞

# 思维 #

可以想到，速度慢的车一定会堵住他后面速度比他快的车，所以在到达终点线的时候，0车也可能会被前面的车堵住。

假设在0车之前有一辆车x，他的速度比x+1车要慢，且比\[i...x-1\]车速度也要慢，那么他可作为当下后面所有车的那辆车。

那么其实无论\[i..x-1\]的车发生怎样的变化，在这断变化直到追上x车的时间，都是x在离终点线走的路程的一部分，之后x继续走完全程，这时候如果0车也在被堵住的车内，那么花费的时间其实就是x车以他自己的速度走完的时间+0车以x车速度走完0车与x车之间的车身长。

但是如果在追上x车之前，x车已经走过终点了怎么办呢？那说明在x车之前有一辆车把他后面的车堵住了，这种情况和之前分析的情况又变成一样的了。

所以我们把每辆车都当成最前面的车，计算到终点的时间以及0车按照该车速度走完前面车身的时间，取最大值即可.

#include <bits/stdc++.h>
    #define INF 0x3f3f3f3f
    #define full(a, b) memset(a, b, sizeof a)
    #define FAST_IO ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
    using namespace std;
    typedef long long LL;
    inline int lowbit(int x){ return x & (-x); }
    inline int read(){
        int ret = 0, w = 0; char ch = 0;
        while(!isdigit(ch)){
            w |= ch == '-', ch = getchar();
        }
        while(isdigit(ch)){
            ret = (ret << 3) + (ret << 1) + (ch ^ 48);
            ch = getchar();
        }
        return w ? -ret : ret;
    }
    inline int lcm(int a, int b){ return a / __gcd(a, b) * b; }
    template <typename A, typename B, typename C>
    inline A fpow(A x, B p, C lyd){
        A ans = 1;
        for(; p; p >>= 1, x = 1LL * x * x % lyd)if(p & 1)ans = 1LL * x * ans % lyd;
        return ans;
    }
    const int N = 200005;
    int n;
    double l[N], s[N], v[N];
    
    int main(){
    
        while(~scanf("%d", &n)){
            for(int i = 0; i <= n; i ++) scanf("%lf", &l[i]);
            for(int i = 0; i <= n; i ++) scanf("%lf", &s[i]);
            for(int i = 0; i <= n; i ++) scanf("%lf", &v[i]);
            double cur = 0, ans = 0;
            for(int i = 0; i <= n; i ++){
                if(i != 0) cur += l[i];
                double t = (s[i] + cur) / v[i];
                ans = max(ans, t);
            }
            printf("%.10lf\n", ans);
        }
        return 0;
    }

转载于:https://www.cnblogs.com/onionQAQ/p/11231921.html