自动搬运

查看原文

来自洛谷，原作者为

	qjyzLfy 渐行、渐远，渐觉…

搬运于2025-08-24 22:10:31，当前版本为作者最后更新于2020-05-25 01:49:30，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

分析

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;
}