Traffic Management Gym - 101875G-白红宇

Traffic Management Gym - 101875G

阅读量：4967 次

发布时间：2019-06-12

本文共 954 字，大约阅读时间需要 3 分钟。

题意：

有n辆车，在一条直线上运动，给定位置和速度。如果后车追上前车，则后车不会超车，而已变成前车的速度前进，问最后一次上述车速变化发生在何时。

思路：

假设有一下车辆，数字代表移动速度，具体位置未知，但是相对未知就是数字的摆放顺序，车辆移动方向为右,车辆用速度代称；

　　　　　　　　8 　　4 　　3 　　5 　　2 　　 6　　7

由此可知，以2为分界线，2左边的车，速度再快也追不上右边的车，因为已经被2拦住了。

但是3左边的车还是可以追上2-3之间的车(车5)。

实际上不难看出，如果车速是num,而i到n中车速最小的就是num[i]的话，那么num[i]左边的都不能追上num[i]右边的了。

所以我们需要从右向左更新最小值，并且更新答案。

再考虑

　　　　4　　3　　2

4一定会追上2，但是有两种方式。

1.先追上3，再以速度3追上2.

　　这种情况的时间就是3追上2的时间。

2.3先追上2，然后才被4追上。

　　这种情况的时间就是4追上2的时间，可以忽略3。

由此可知，只要简单算出左边到最小值的时间就行了。

注意这个最小值对于某一辆车来说，是它右边所有数的最小值呦！

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #define fuck(x) cout<<#x<<" = "<
                 
                  <
                  
                   =0;i--){ if(a[i].v<=a[m].v){m=i;} else{ans=max(ans,1.0*(a[m].s-a[i].s)/(a[i].v-a[m].v));} } printf("%.6f\n",ans); return 0;}

View Code

转载于:https://www.cnblogs.com/ZGQblogs/p/10476986.html

你可能感兴趣的文章