hdu多校第一场1004（hdu6581）Vacation 签到

题意：有n+1辆车，每辆车都有一定的长度，速度和距离终点的距离，第1-n辆车在前面依次排列，第0辆车在最后面。不允许超车，一旦后车追上前车，后车就减速，求第0辆车最快什么时候能到达终点？

思路：对于每一辆车，假想它被后面的所有车追上，连成一个长串，这一长串以该车的速度行驶，这一长串的尾巴通过终点的时间。

但是实际上不是所有的车都能连成这样一个长串并以自己的速度前进，可能太快了导致后面的车追不上它，也可能太快了导致速度被前车限制，因此对于每一辆车求出理想状态下连成的长串花费时间，其最大值为解。

时间复杂度O（n）

代码：

#include <bits/stdc++.h>

#pragma GCC optimize(2)

using namespace std;

typedef long long LL;

#define ls (rt<<1)

#define rs (rt<<1|1)

const int M = 1e5 + ;

const LL mod = 1e9 + ;

const double eps = 1e-;

const double pi = acos(-);

const int INF = 0x3f3f3f3f;

const int maxn = 2e5 + ;

const int N = ;

int n;

LL s[M], l[M], v[M];

double ans;

int main()

{

    while (~scanf("%d", &n))

    {

        for (int i = ; i <= n+; i++)

        {

            scanf("%lld", &l[i]);

        }

        for (int i = ; i <= n+; i++)

        {

            scanf("%lld", &s[i]);

        }

        for (int i = ; i <= n+; i++)

        {

            l[i] = l[i] + l[i - ];

        }

        for (int i = ; i <= n+; i++)

        {

            scanf("%lld", &v[i]);

        }

        ans = (double)1.0*s[] / v[];

        for (int i = ; i <= n+; i++)

        {

            double tmp = 1.0*(l[i] + s[i]) / v[i];

            ans = max(tmp, ans);

        }

        printf("%.10f\n", ans);

    }

}