2019 Multi-University Training Contest 1 1004 Vacation
思维题 模拟   发布于 2019-07-23   374人围观  0条评论
思维题 模拟   发表于 2019-07-23   374人围观  0条评论

题目大意

Tom和Jerry开着0号车,前面依次有1……n号车,且不能超车。

给出每个车的长度、距离停车线的长度、最大行驶速度,求出0号车头部通过停车线的时间。

注意:车开过停车线后依旧不能超车。

题解

正解实际上时用堆(优先队列)来维护各个车的追及时间以及距离什么的,时间复杂度时O(nlogn),而且非常难写。

听说他们有很多用二分做出来的,也不是很清楚怎么check的

这里有一个思维量稍大但代码简单的O(n)的做法。

首先我们要知道,每辆车开过停车线后依旧在走,不能超车,也就是即使此车开过停车线,也是可以堵住后面的车的。

第二点我们要知道的,就是如果前一辆车的尾部没有开过停车线,那么后面的车一定无法开过停车线(虽然看起来很显然,但是这其实是个关键点)。

然后我们考虑如果我们的车被堵了,比方前面所有车被i号车堵住了,那么我们的最少需要的通过时间是多少?

答案是i号车距离停车线的长度加上后面所有车(除去0号车)的长度除以i号车的最大速度。

因为后面的车都被i号车堵住了,所以他们都要按照i号车最终的的速度去通过停车线。

于是我们只需要这样对1……n号车算一遍时间,最后与0号车距离停车线的长度除以其最大行驶速度的值取个最大值就可以了。

代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
const int maxn = 1e6+5;
int n;
double l[maxn],s[maxn],v[maxn],t[maxn];
int main(){
    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]);
        t[0] = s[0] / v[0];
        double ans = t[0];
        for(int i = 1;i <= n;++i){
            if(i != 1)
                l[i] += l[i-1];
            t[i] = (s[i] + l[i]) / v[i];
            ans = max(ans,t[i]);
        }
        printf("%.10lf\n",ans);
    }
    return 0;
}


上一篇: 2019 Multi-University Training Contest 1 1005 Path 最小割+最短路

下一篇: Educational Codeforces Round 69 D Yet Another Subarray Problem 思维题

立即登录,发表评论
没有帐号?立即注册
0 条评论