杭电多校第一场 D - Vacation

• 题意：

• 给出n+1辆车，给出每辆车距离动物园的距离，速度，车长度，距离动物园最远的是你所在的车，当前后俩车相遇的时候，会合并，并以速度较小的车的移速接着行驶，问你自己的车车头到达动物园需要多少时间。

• 题解：

• 这题一开始想着模拟，但确实有些麻烦。

• 简单做法，也是最神奇的做法：最终通过停止线的时候，一定是一个车后面堵着剩余所有的车，那么影响时间的就只有最前面这辆车，所以对于每一辆车，假设是它是和 0 车堵在一起的最靠前的一辆车，那么可以计算出一个值，所有的车的计算值的最大值就是答案。

• 代码：

  #include <bits/stdc++.h>
  using namespace std;
  struct node{
    double s,len,v,t;
  }a[100010];
  bool cmp(node p1,node p2)
  {
    return p1.s < p2.s;
  }
  int main()
  {
    int t;
    double len1,s1,v1;
    while(~scanf("%d",&t) && t)
    {
  
        double k = 0;
        scanf("%lf",&len1);
        for(int i=1;i<=t;i++)
        {
            scanf("%lf",&a[i].len);
            k += a[i].len;
        }
        scanf("%lf",&s1);
        for(int i=1;i<=t;i++){
            scanf("%lf",&a[i].s);
        }
        scanf("%lf",&v1);
        for(int i=1;i<=t;i++){
            scanf("%lf",&a[i].v);
            a[i].t = a[i].s/a[i].v;
        }
        double ans = s1/v1;
        sort(a+1,a+1+t,cmp);
        for(int i=1;i<=t;i++)
        {
            double t1 = a[i].s/a[i].v;
            double t2 = k/a[i].v;
            t1 += t2;
            k -= a[i].len;
            ans = max(ans,t1);
        }
        printf("%.9lf\n",ans);
    }
    return 0;
  }
  

```