2019多校第一场 HDU6581 - Vacation（思维）

链接：HDU6581 - Vacation

题意：

一排车过停止线，给出车的长度 l ，车头到停止线的距离 s，车的最高速度 v 。每辆车都以最高速度v行驶，但是若和前车间距为0时，速度无法超过前车（即会与前车保持一致速度）。

现TOM的车（标号为0）前方有n辆车（标号为1 ~ n）。问TOM最少要多久才能到达停止线？

注意：即使车过了停止线也仍然在路上（即会阻碍到后面的车）

分析：

看了题解才知道最简单的方法时间复杂度居然只有O(N)…

对于TOM的车（0号车），当车头到达停止线时，一种情况 是 0号车前面没有车，则时间为
$$t=s[0]/v[0]$$

另一种情况 就是 0号车前面有车（即已经和前面一些车合并了），假设这些车最前面一辆是 i 号车。
（如下图，i = 2）

由于 i 号车是这些车合并后的车头，那么说明从 开始 到 0号车到达停止线 为止，i号车的速度一直没变，那么这段时间可以求得为：
$$t=(s[i]+\sum _{j=1}^{i}l[j])/v[i]$$

枚举 i 求出 t，最后 最大的 t 就是答案。因为当 t 更大说明 0号车从开始到停止线的速度相对更慢（距离都是s[0]），速度更慢说明 前面有更慢的车挡住了，那么 其他 t 更小的假设就不成立了。

以下代码：

#include<bits/stdc++.h>
#define PII pair<int,LL>
#define LL long long
using namespace std;
const LL INF=0x3f3f3f3f;
const int maxn=1e5+50;
int main()
{
    int n;while(~scanf("%d",&n)){
    double l[maxn],s[maxn],v[maxn];double suml[maxn];for(int i=0;i<=n;i++){
    scanf("%lf",&l[i]);     if(i==0)suml[i]=0;elsesuml[i]=suml[i-1]+l[i];}for(int i=0;i<=n;i++)scanf("%lf",&s[i]);for(int i=0;i<=n;i++)scanf("%lf",&v[i]);double ans=0;for(int i=0;i<=n;i++){
    double t=(s[i]+suml[i])/v[i];ans=max(ans,t);}printf("%.10f\n",ans);}return 0;
}