2019 Multi-University Training Contest 1

思维

可以想到,速度慢的车一定会堵住他后面速度比他快的车,所以在到达终点线的时候,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
", ans);
    }
    return 0;
}
原文地址:https://www.cnblogs.com/onionQAQ/p/11231921.html