2019杭电多校赛第一场 1004 Vacation
题目链接: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; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |