加入收藏 | 设为首页 | 会员中心 | 我要投稿 李大同 (https://www.lidatong.com.cn/)- 科技、建站、经验、云计算、5G、大数据,站长网!
当前位置: 首页 > 站长学院 > PHP教程 > 正文

2019杭电多校赛第一场 1004 Vacation

发布时间:2020-12-13 22:17:57 所属栏目:PHP教程 来源:网络整理
导读:题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=6581 题意:在一条狭窄的通道上有n+1辆车依次排列(我们是第0辆车),每个车具有车长,距终点的距离,以及车速,不能超车,也就是说你的车速受到前面车的控制,问第0辆车想通过终点线的最短距离是多少

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=6581

题意:在一条狭窄的通道上有n+1辆车依次排列(我们是第0辆车),每个车具有车长,距终点的距离,以及车速,不能超车,也就是说你的车速受到前面车的控制,问第0辆车想通过终点线的最短距离是多少

分析:杜老师的正解是用的二分答案做的,非常复杂,很多人写出了O(N)的写法,写成了思维题。

我们可以分析,最后一辆车肯定最终会依附前面的一辆车(全程自己跑的情况我们看做依附自己,单独求),确定这一点后,中间非常复杂的分析过程我们就可以不用了,直接根据依附的车的速度来算,因为我们可以确定依附的车肯定是越往前越快(因为后面的车肯定是速度不如前车或者距离太大追不上),所以我们依附的这辆车肯定是按照全速在跑,所以我们可以每个车都枚举一遍(看做是被依附的车)来算时间(注意,因为求的是最后一辆车的时间,距离应该是被依附的车距终点距离和依附的所有车的长度,因为最后一辆车都依附的情况下,中间的所有车肯定也依附了),所有时间都算完后,我们取最大值。这里很重要,因为题目要求的是最快到达终点的距离,而我们为什么取最大值呢?

因为,只有最大情况才是满足实际要求的,我们想要满足最快时间都是在追上前全速跑,追上后跟随,但以我们的模型,都是在枚举到一个车时只考虑它当前的情况, 不考虑它会不会又追上了一个车,导致本命中间该降速的,但是仍在一直往前冲,或者是最后一辆车速度特别快,其实后面的车根本追不上了,速度也虚快。所以唯有最大值才是符合实际情况的。

#include <bits/stdc++.h>
using namespace std;
const int inf=1<<30;
typedef long long ll;
typedef pair<int,int> P;
const double pi=acos(-1);
const int mod=1e8+7;
const int maxn=1e5+7;
const int maxm=1e5;
int s[maxn],l[maxn],v[maxn];
int main(){
    int n;
    while(cin>>n){
        for(int i=0;i<=n;i++)scanf("%d",&l[i]);
        for(int i=0;i<=n;i++)scanf("%d",&s[i]);
        for(int i=0;i<=n;i++)scanf("%d",&v[i]);
        //cout<<s[0]<<" "<<v[0]<<endl;
        double ans=s[0]*1.0/v[0];
        //cout<<ans<<endl;
        int tmp=0;
        for(int i=1;i<=n;i++){
            tmp+=l[i];
            ans=max(ans,(s[i]+tmp)*1.0/v[i]);
        }
        printf("%.10lfn",ans);
    }
    return 0;
}

(编辑:李大同)

【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容!

    推荐文章
      热点阅读