Vacation

update(O(n))

看了那个O(n)的方法，感觉自己想的那个O(nlogn)的好傻，awsl。

0车最终通过停车线的时候，状态一定是某个车堵住后面的所有车(这个车也可以是0车)。所以我们要找的就是那个把后面所有都堵住的最前面的车x，x车没有被别的车堵住，从头到尾都按照初始速度行驶，当0车到停车线时，这x车走过的距离d = s_x + 0到x车的车身长度和，时间为d/v_x。

我们假设所有的车都是车x，求出时间，其中最大时间即为答案。因为如正确的时间t = (车i行驶的总路程/车i的平均速度).如果一辆车的速度改变过，只会变小，而用原来的速度算会使答案偏小，而如果这辆车在车x的前面，与x有一段距离，那参与运算的d就偏小了，算出的时间就会偏小。

以下为代码

#include <bits/stdc++.h>

#define INF 0x3f3f3f3f

using namespace std;

typedef long long ll;

const int N = 100005;

double l[N], s[N], v[N];

double len[N];

int main()

{

    int n;

    while(scanf("%d", &n) != EOF){

        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]);

        len[0] = 0;

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

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

        double ans = 0.0;

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

            ans = max(ans, (s[i] + len[i]) / v[i]);

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

    }

    return 0;

}

解题思路(O(nlog)n)

一开始的时候所有车都是是按照自己原来的速度行驶，直到有一辆车x追上前面的那辆车y，此时的变化只有，1.x的速度变为y的速度2.x后面的车追上x的时间变短。所以我们只要利用优先队列，每一次都找到会在最短的时间内追上前面那辆车的x，不断更新这个过程就好了。

以及实现中的一些细节，1.对于已经追上和被追上的两辆车，我们可以看成一辆火车，每辆车就是一节车厢，其速度就是最前面那节车厢的速度，当一辆火车追上另一辆的时候，新的火车头就是前面被追上车厢的火车头，新的火车尾就是后面火车的火车尾，所以我们记录每节作为火车头的车厢对应的火车尾，和每节火车尾对应的火车头。2.优先队列中的时间指是第几秒会追上前面的车。由于前面的车会变速，所以要记录上一次变速的时间，以及上一次变速前已经走了多少或还剩下多少距离。3.只有后面的车可以追上前面的车时才进队。

还有就是，不要直接memset，数据组数很多，会超时。

代码如下

#include <bits/stdc++.h>

#define INF 0x3f3f3f3f

using namespace std;

typedef long long ll;

const int N = 100005;

double len[N], s[N], v[N];

int l[N], r[N];

struct T{

    double t;

    int x;

    T(int x, double t): x(x), t(t){}

    bool operator<(const T& a)const{

        return t > a.t;

    }

};

bool vis[N];

double t[N], dis[N];

int main()

{

    int n;

    while(scanf("%d", &n) != EOF){

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

            scanf("%lf", &len[i]);  //车长

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

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

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

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

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

            l[i] = r[i] = i;

        priority_queue<T> pq;

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

            t[i] = 0.0;

            vis[i] = false;

            dis[i] = s[i] - s[i + 1] - len[i + 1];

            if(v[i] > v[i + 1])

                pq.push(T(i, dis[i] / (v[i] - v[i + 1])));

        }

        double d = 0.0;  //0号车已走的路程

        double last = 0.0;

        while(!pq.empty()){

            T top = pq.top();

            pq.pop();

            if(vis[top.x])

                continue;

            vis[top.x] = true;

            double time = top.t;

            int x = top.x;

            if(d + v[r[0]] * (time - last) >= s[0])

                break;

            d += v[r[0]] * (time - last);

            r[l[x]] = r[x + 1];

            l[r[x + 1]] = l[x];

            if(l[x] != 0){

                dis[l[x] - 1] -= (time - t[l[x] - 1]) * (v[l[x] - 1] - v[x]);

                t[l[x] - 1] = time;

                if(v[l[x] - 1] > v[r[x + 1]])

                    pq.push(T(l[x] - 1, time + dis[l[x] - 1] / (v[l[x] - 1] - v[r[x + 1]])));

            }

            last = time;

        }

        printf("%.10f\n", last + (s[0] - d) / v[r[0]]);

    }

    return 0;

}

巴特西

2019杭电多校第一场hdu6581 Vacation

Vacation

update(O(n))

以下为代码

解题思路(O(nlog)n)

代码如下

最新文章

热门文章