题解：P5413 [YNOI2019] 骑单车

DGFLSzfd · 2024-07-31 22:49:40 · 题解

2024.7.31 晚终于将此题做对，写此题解以记录思路和过程。\ 以后谁再说普及 - 是水题，我一定让他看这题。(偷偷流泪) （求通过，各种问题改了10次了）

浅谈此题

本题是我认为最优秀的跨学科题目之一，采用了信息技术贪心的解题方式，数学的分类讨论思维以及物理的公式熟练运用。

知识前置

注：高中生可以直接跳过

对于初中生、小学生而言，我认为这题完全可以评到普及 + 一旦你学完物理必修（一）的加速度，这题便会难度骤降。\ 本题适合各位同时热爱信息和物理的同学挑战！

知识点一：加速度的概念

请先观看【高中物理必修（一）1.4 加速度】。\ 看完该该视频你应该已经初步了解了什么是加速度了。

1. 加速度是描述速度变化快慢的物理量（米每秒每秒）。
2. 加速度的物理含义是描述速度变化的快慢。
3. 加速度等于速度的变化除以相应的变化时间。\ （即: \large a\text{(加速度)}=\frac{V\text{(当前速度)}-V_{0} \text{(初始速度)}}{t\text{(变化时间)}})

知识点二：加速度相关的公式以及推导过程

1. 匀变速直线运动的速度与时间关系的公式 {\large V_{t}=V_{0}+at}

2. 平均速度 {\large \overline{V}(\text{平均速度})= \frac{(V_{0}+V)} 2}

3. 时间与速度变化的关系(由加速度定义式转变而来){\large t\text{(变化时间)}=\frac{V_{t} \text{(当前速度)}-V_{0}\text{(初始速度)}}{a\text{(加速度)}} }

4. 匀变速直线运动的位移与时间关系的公式 {\large S=v_{0} t+\frac 1 2 a t^{2}}\ 推导过程如下：\ 已知 {\large S=\overline{V} \times t}\ 代入②后得 {\large S=\frac{(V_{0}+V)} 2 \times t}\ 代入①后得 {\large S=\frac{(V_{0}+V_{0}+at)}2 \times t}\ 将式子展开得：{\large S=v_{0} t+\frac1 2 \times a t^{2}}

5. 匀变速直线运动的位移与速度关系的公式 {\large 2aS=v_{t}^{2}-v_{0}^{2}}

6. 推导过程如下：\ 已知 {\large S=\overline{V} \times t}\ 代入②后得 {\large S=\frac{(V_{0}+V)}2 \times t}\ 代入③后得 {\large S=\frac{(V_{0}+V)}2 \times \frac{V_{t}-V_{0}}{a}}\ 将式子展开得 {\large 2aS=v_{t}^{2}-v_{0}^{2}}\ 将式子形变可得 {\Large S=\frac {v_{t}^{2}-v_{0}^{2}}{2a}}（本篇最重要的公式！）\ 相信聪明的你到此一定对物理有了更深刻的了解！

思路推理

寻找目标

观察题目后不难发现，我们应当找出一个计算方法，分别计算再统计总数。所以接下来的思路推理应着重于思考如何计算通过一段路的最短时间。\ 我门对一段路，现已知初始速度（也就是离开上一段路的速度）speed(m/s)、本段路的限速 S(m/s)、离开这段路的限速 V_{next}（也就是下一段路的限速)、本段路的长度 w(m)、本段路的最大加速度的绝对值 a(m/s^{2})\ 我们既然要求时间，那我们就必须知道速度峰值 V。

推理影响因素

然而对于一段路的速度峰值 V 实则是受到以下四个因素影响的：

1. 本段路限速\ 这是显而易见的，毕竟你开的再快也不能超速。
2. 下一段路的限速\ 同样，为了你能够符合要求的进入下一段路，离开时我们应把速度调整至合法的状态，峰值太高离开时可能刹不住车！
3. 初始速度与加速度\ 你速度的峰值取决于你的能力上限，极有可能你就算整条路都在加速你的峰值也很低。
4. 下下段路限速\ 你由本段路进入下段路时符合当前限速，但是下段路就算一直减速也无法减到下下一段路的限速之内。因此我们还要考虑下下段路的峰值。（我们应对峰值按此倒着预处理，使一段路的峰值受到其后面所有路的约束）

基本理论想法

通过观察公式：匀变速直线运动的位移与时间关系的公式

不难发现在路程相同的情况下加速度 a 越大时间 t 越小。\ 由此我们得出结论，要想时间少，只要变速，就必须是 a_{max}

答案计算

在受到条件①③④（①③④都是可以直接预处理的）的约束后，显然一段路的最短时间为

但是你会发现

也许会大于这段路的长度。\ 没错！我们还要根据下一段路的限速寻找一个合法的峰值速度！

判定合法方式一

回顾前置知识中，匀变速直线运动的位移与速度关系的公式

以及其变式

我们可知当前峰值下 S_{V}=S_{加速}+S_{峰值速度匀速}+S_{减速}\ 认定该峰值合法则需 S_{V}\le S(该段路的长度)

判定合法方式二

注：V_{1} 是离开速度限速。\ 寻找仅仅离开速度限速的影响下的最大峰值。\ 要使 V 尽量大则 S_{V} 需尽量大。\ 则要使 S_{V}=S 展开为

经简化得 V_{MAX}=\sqrt{\frac{\left(2as+V_{0}^{2}+V_{1}^{2}\right)} 2}\ 若 V_{MAX}<V(只条件①③④约束) 则不合法，否则合法。\ (注：选择一种方式判定即可，作者的代码中选用了第一种)

情况一 在受到条件①③④的影响下峰值是合法的

情况一我们确定该峰值合法。则 ans+=\frac{V-V_{0}}{a}+\frac{S-S_{加速}-S_{减速}}{V}+\frac{V-V_{1}}{a}

情况二 仍需下调寻找峰值速度

由于当前的 S_{V} 不合法，我们应重新计算和法值。\ 因为需 S_{V}\le S(该段路的长度) 要使 V 尽量大则 S_{V} 需尽量大。\ 则要使 S_{V}=S。展开为

经简化得 V_{MAX}=\sqrt{\frac{\left(2as+V_{0}^{2}+V_{1}^{2}\right)} 2}\ 则 ans+=\frac{V-V_{0}}{a}+\frac{V-V_{1}}{a}

细节整理

speed 的初值 ：因为 speed 是初始速度，那么应该是上一条路结束速度与这一条路限速的较小值。\ V_{next} 的初值 ：因为 V_{next} 是结束时的速度，所以应该是这条路与下一条路的限速的较小值。

代码展示

我最喜欢的环节

#include<bits/stdc++.h>
using namespace std;

const int N=1e2+10;

struct rode_node
{
    long double w,v,a;//注意long double 存储！！！ 
} r[N];
int T;
int main()
{
    cin>>T;
    while(T--)
    {
        int n;cin>>n;
        for(int i=0;i<n;i++) cin>>r[i].w>>r[i].v>>r[i].a;//处理影响因素① 

        long double ans=0.0,speed=0.0;
        for(int i=n-2;i>=0;i--) 
            r[i].v=min(r[i].v,sqrt(2.0*r[i].a*r[i].w+r[i+1].v*r[i+1].v));//处理影响因素④ 
        r[n].v=r[n-1].v;//对于离开最后一段路时，无需把速度降为0，所以n+1段路的限速可以随便设置一个大数 

        for(int i=0;i<n;i++)
        {
            r[i].v=min(r[i].v,sqrt(2.0*r[i].a*r[i].w+speed*speed));//处理影响因素③ 

            long double v_next=min(r[i].v,r[i+1].v);//离开这段路的限速
            long double speed_up  =(speed+r[i].v) *(r[i].v-speed) *0.5/r[i].a;//初始速度加速到峰值的路程 
            long double speed_down=(v_next+r[i].v)*(r[i].v-v_next)*0.5/r[i].a;//峰值减速到限速的路程 

            if(r[i].w>=speed_up+speed_down)//情况一、足够加速到峰值再减速 
            {
                ans+=(r[i].v-speed)/r[i].a+
                    (r[i].v-v_next)/r[i].a+//原理见时间与速度变化的关系 
                    (r[i].w-speed_up-speed_down)/r[i].v;
                speed=v_next;
            }
            else//情况二、加速到一定时候就得减速 
            {
                long double v_max=sqrt( (2.0*r[i].a*r[i].w+pow(speed,2)+pow(v_next,2) ) /2 );//处理影响因素② 
                ans+=((v_max-speed)/r[i].a+(v_max-v_next)/r[i].a);
                speed=min(v_max,r[i+1].v);
            }
        }cout<<ans<<endl;
    }
    return 0;
}