题解 P5413 【[YNOI2019]骑单车】

· · 题解

分析

1

加速时，显然小明一定会用最快的加速度；然后，小明一定会在较高的速度下保持尽量长的时间，所以要尽量缩短减速时间，因此减速时也会用最大加速度。

为了更好地证明这一观点，可以作小明的 \text{v-t} 图像，图像面积即为路程，斜率即为加速度。显然，面积一定，要使时间尽量小，就要使图像尽量“凸”，所以要使加速度尽量大。

2

高中运动学公式。对于匀加速直线运动，有：

|{v_1}^2-{v_2}^2|=2ax

证明：

x = \bar{v}t=\dfrac{v_1+v_2}{2}\cdot\dfrac{|v_1-v_2|}{a}=\dfrac{|{v_1}^2-{v_2}^2|}{2a}

去分母即得上公式。

3

小明会让自己的速度尽量大，但是各种客观条件会限制他的速度的上限。

具体来说，在某一段路上，除了不能超过限速之外，还要保证小明可以不超过限速地进入之后的路。也就是，不能发生下面的情况：

显然，为了不在之后的路上超速，小明在每段路的末尾都会有一个最大的允许速度 vr 。vr 受到这段路之后的路的限速和加速度的限制。

显然，小明在每段路的开端也都会有一个最大的可能速度 vl ， vl 受到这段路之前的路的限制。对于相邻的两段路，前一段的 vr 等于后一段的 vl 。

4

如果确定了一段路的 vl 和 vr ，这段路中间小明的最优的运动方式就可以确定，而不受其它路段的影响了。

经过上面的分析， vl 和 vr 所受的约束仅有 \begin{cases}vr_i=vl_{i+1}\\vr_i,vl_i\le lim_i\\|{vl_i}^2-{vr_i}^2|\le 2a_i\cdot len_i\end{cases} 。

其中 lim_i 为限速， len_i 为路的长度。

第三式（以加速的情况为例）的原理是：左式对应一直加速所需的路程，右侧对应实际路程。显然，中间有某一部分不加速，或者先加速又减速，都会使对应路程更长。

5

由于没有一定的优先顺序，可以先把 vl,vr 都定为 lim ，然后根据约束逐步缩小，直到不可缩小为止。

显然，如果还未得到满足所有约束的 vl,vr ，则当前解状态一定有 vl 或 vr 可以被缩小；当 vl,vr 不可根据约束缩小时，即得到最优解。

之后再算出各段路内部花费的时间即可。

6

一段路内部的情况只可能有两种：

可以先分别算出从初速加速到限速和从限速减速到末速所需的路程 tx1,tx2 ，如果路程之和大于 len_i 就是第二种情况。

第一种情况容易解决：

t=\dfrac{v_{lim}-v_{vl}}{a}+\dfrac{x_{len}-x_{tx1}-x_{tx2}}{v_{lim}}+\dfrac{v_{lim}-v_{vr}}{a}

对于第二种情况，设加速到的最大的速度为 vm ，有：

\dfrac{{v_{vm}}^2-{v_{vl}}^2}{2a}+\dfrac{{v_{vm}}^2-{v_{vr}}^2}{2a}=x_{len} \Rightarrow \ {v_{vm}}^2=a\cdot x_{len}+\dfrac{{v_{vl}}^2+{v_{vr}}^2}{2}

而 t=\dfrac{v_{vm}-v_{vl}}{a}+\dfrac{v_{vm}-v_{vr}}{a}=\dfrac{2v_{vm}-v_{vl}-v_{vr}}{a}

代码

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

int t,n;
double len[111],lim[111],a[111];
double vl[111],vr[111];
double ans;
double tv,tx1,tx2;//临时用的变量. 
bool flag; 

int main()
{
    scanf("%d",&t);
    vr[0]=0;//必须从0开始加速. 
    while(t--){
        scanf("%d",&n);
        vl[n+1]=1111;//方便约束 vr[i] 和 vl[i+1] 的关系. 
        for(int i=1;i<=n;++i){
            scanf("%lf%lf%lf",&len[i],&lim[i],&a[i]);
            vl[i]=vr[i]=lim[i];
        }
        do{//缩小 vl 和 vr. 
            flag=0;
            for(int i=1;i<=n;++i){
                if(vl[i]>vr[i-1])   vl[i]=vr[i-1],flag=1;
                if(vr[i]>vl[i+1])   vr[i]=vl[i+1],flag=1;
                if(vl[i]<vr[i]){//用较小的约束较大的,而不是相反. 
                    tv=sqrt(vl[i]*vl[i]+2.0*a[i]*len[i]);// 
                    if(vr[i]>tv)    vr[i]=tv,flag=1;
                }
                else{
                    tv=sqrt(vr[i]*vr[i]+2.0*a[i]*len[i]);
                    if(vl[i]>tv)    vl[i]=tv,flag=1;
                }
            }
        }while(flag) ;//flag==0 说明无法继续收缩. 
        ans=0;
        for(int i=1;i<=n;++i){
            tx1=(lim[i]*lim[i]-vl[i]*vl[i])/(2.0*a[i]);
            tx2=(lim[i]*lim[i]-vr[i]*vr[i])/(2.0*a[i]);
            if(tx1+tx2>len[i]){//无法加速到限速.
                tv=sqrt(a[i]*len[i]+(vl[i]*vl[i]+vr[i]*vr[i])*0.5);//此处 tv 即文章中 vm 
                ans+=(tv+tv-vl[i]-vr[i])/a[i];
            }
            else{//可以加速到限速. 
                ans+=(lim[i]+lim[i]-vl[i]-vr[i])/a[i]+(len[i]-tx1-tx2)/lim[i];
            }
        }
        cout<<ans;
    }
    return 0;
}