hdu 6851 Vacation(思维+贪心)
2024-09-03 15:27:18
•题意
有编号0到n,n+1辆车排队过红绿灯,从0到n离交通灯线越来越近
每辆车都有一个最大速度v,车身长度l,和离交通灯线的距离s,
一辆车头到达线则说明这辆车已到达线
如果一辆车前面没有紧邻着一辆车,那么这辆车可以以最大速度行驶
如果前面紧邻着一辆车,则车头贴着前一辆车尾行驶,不能超车!
即使过了交通灯线也不能超车!
问第0辆也就是离线最远的一辆,到达线的最短时间
•思路
既然不能超车,那么最远的车到线时有两种可能
①自己到线 $t=\frac{s_{0}}{v_{0}}$
②接在第p辆车后面到线 $\frac{s_{p}+\sum_{1}^{p}l_{i}}{v_{p}}$
解释一下接在某辆车后面为什么是这样算
假设有两辆车$a_{1}$速度为$v$,$a_{0}$速度为$2v$
当前面的车到达$p$点时,同时后面的车到达${p}'$ ,两者所花时间相同
同理可知
当$a_{1}$到达$O$点时,$a_{0}$到达$l_{1}$点,也就是$a_{0}$离终点线的距离是$a_{1}$的车长
②式也就是如果连在了第$p$辆车后面($p$后面的车全都连起来了)
当第$p$辆车到达终点线时,最远的一辆车离终点线的距离就是$p$后面所有车的车长-最后一辆车自身车长
也就是$sum=\sum_{1}^{p}l_{i}$
所以行驶的时间就是$p$车行驶时间+最远的车以$v_{p}$行驶$sum$的时间即$\frac{s_{p}}{v_{p}}+\frac{\sum_{1}^{p}l_{i}}{v_{p}}$
由于接在那辆车后面不确定,所以可以算最大的时间,
行驶时间长说明速度慢,后面速度快的肯定会接在他后面
•代码
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+;
double l[maxn],s[maxn],v[maxn];
double sum[maxn];
int main()
{
int n;
while(~scanf("%d",&n))
{
for(int i=;i<=n;i++)
{
scanf("%lf",&l[i]);
if(i==)
continue;
sum[i]=sum[i-]+l[i];
}
for(int i=;i<=n;i++)
scanf("%lf",&s[i]);
for(int i=;i<=n;i++)
scanf("%lf",&v[i]); ///单独过终点
double ans=s[]/v[]; ///排队过终点
for(int i=;i<=n;i++)
ans=max(ans,(s[i]+sum[i])/v[i]); printf("%.10f\n",ans);
}
}
最新文章
- I/O Directory类
- Java多线程理解
- Hibernate Validator验证标签说明
- java 中的fanal
- BZOJ 3224 普通平衡树(树状数组)
- IOS 解析歌词lrc
- Java单例模式的线程安全问题
- HDU 4931 Happy Three Friends(水)
- 深挖BAT内部级别和薪资待遇,你敢看?(转)
- JavaWEB开发国际化
- 从NPM到CNPM
- C/C++生成随机数
- sql的查询语句的总结
- [LeetCode] Inorder Successor in BST II 二叉搜索树中的中序后继节点之二
- 页面中dropDownListt的二级关联
- ELK Stack 5.2.2 安装文档
- 默认情况下eth0网卡配置文件路径及客户端DNS的路径
- MongoDB 简单上手
- linux内核分析 第四周 扒开系统调用的三层皮(上)
- bzoj-1492 货币兑换Cash (2)——CDQ分治