E、蜗牛（时间限制: 1.0s 内存限制: 512.0MB）
【问题描述】
这天，一只蜗牛来到了二维坐标系的原点。 在 x 轴上长有 n 根竹竿。它们平行于 y 轴，底部纵坐标为 0 ，横坐标分别 为 x 1 , x 2 , ..., x n 。竹竿的高度均为无限高，宽度可忽略。蜗牛想要从原点走到第 n 个竹竿的底部也就是坐标 ( x n , 0) 。它只能在 x 轴上或者竹竿上爬行，在 x 轴
上爬行速度为 1 单位每秒；由于受到引力影响，蜗牛在竹竿上向上和向下爬行 的速度分别为 0 . 7 单位每秒和 1 . 3 单位每秒。 为了快速到达目的地，它施展了魔法，在第 i 和 i + 1 根竹竿之间建立了传 送门（0 < i < n ），如果蜗牛位于第 i 根竹竿的高度为 a i 的位置 ( x i , a i ) ，就可以 瞬间到达第 i + 1 根竹竿的高度为 b i +1 的位置 ( x i +1 , b i +1 )， 请计算蜗牛最少需要多少秒才能到达目的地。
【输入格式】
输入共 1 + n 行，第一行为一个正整数 n ；
第二行为 n 个正整数 x 1 , x 2 , . . . , x n ；
后面 n − 1 行，每行两个正整数 a i , b i +1 。
【输出格式】
输出共一行，一个浮点数表示答案（ 四舍五入保留两位小数 ）。
【样例输入】
3
1 10 11
1 1
2 1
【样例输出】4.20
【样例说明】
蜗牛路线：
(0 , 0) → (1 , 0) → (1 , 1) → (10 , 1) → (10 , 0) → (11 , 0) ，花费时间为 1 +1/ 0.7 + 0 + 1/1 .3 + 1 ≈ 4 . 20
【评测用例规模与约定】
对于 20 % 的数据，保证 n ≤ 15 ；
对于 100 % 的数据，保证 n ≤ 10⁵ ，a i , b i ≤ 10⁴ ，x i ≤ 10⁹ 。
非官方题解。
评测链接：蓝桥杯2023年第十四届省赛真题-蜗牛 - C语言网
链接由csdn用户 我为小范 提供。
解题思路:
对于 100 % 的数据，保证 n ≤ 10⁵ ，a i , b i ≤ 10⁴ ，x i ≤ 10⁹ 。
可知 时间复杂度最大为O(n logn);
依据题意，很明显可使用时间复杂度为O(n)的动态规划求解此题。
用door[i]表示第i根竹竿上传送门的高度，pos[i]表示第i根竹竿距离原点的距离。height[i-1]表示从第i-1个传送门传送到第i根竹竿后蜗牛所在的高度；用doorMin[i]表示从原点到达第i根竹竿传送门的最短时间，用footMin[i]表示从原点到达第i根竹竿底部的最短时间。
Scanner scanner = new Scanner(System.in);
int n=scanner.nextInt();
int[] pos=new int[n];//pos[i]表示第i根竹竿距离原点的距离
int[] door =new int[n];//door[i]表示第i根竹竿上传送门的高度
int[] height=new int[n];//height[i]表示从第i个传送门传送到第i+1根竹竿后蜗牛所在的高度
double[] footMin=new double[n];//footMin[i]表示从原点到达第i根竹竿底部的最短时间
double[] doorMin=new double[n];//doorMin[i]表示从原点到达第i根竹竿传送门的最短时间
for (int i=0;i<n;i++)
{
pos[i]=scanner.nextInt();
}
for (int i=0;i<n-1;i++){
door[i]=scanner.nextInt();
height[i]=scanner.nextInt();
}蜗牛要到达第i根竹竿(传送门或底部)，必然要经过第i-1根竹竿。
可知第一根竹竿可以初始化为：
footMin[0]=pos[0]*1.0;
doorMin[0]=pos[0]+door[0]*1.0/0.7;这里先讨论第i根竹竿的传送门距离原点的最小时间doorMin[i]的情况。
从第i-1根竹竿到第i根竹竿的传送门有两种情况:
1.花费doorMin[i-1]的时间到达第i-1根竹竿的传送门，然后到达第i根竹竿的height[i-1]高度，向上或向下爬行(door[i]-height[i-1])/0.7秒或(height[i-1]-door[i])/1.3秒的时间，这里以height[i-1]<=door[i]，向上爬行为例，到达传送门。
2.花费doorMin[i-1]的时间，到达第i-1根竹竿的底部，直接爬行，经过pos[i]-pos[i-1]秒的时间到达 foot[i]=的底部，再向上爬行(door[i]/0.7)秒的时间到达传送门。
得出doorMin[i]的动态转移方程:
以door[i]>height[i-1]为例:
footDistance=pos[i]-pos[i-1];
doorMin[i]=Min(doorMin[i-1]+(door[i]-height[i-1])/0.7, footMin[i-1]+footDistance+door[i]/0.7);
然后讨论footMin[i]的情况：
同理，从第i-1根竹竿到第i根竹竿的底部有两种情况:
1.花费doorMin[i-1]的时间,到达第i-1根竹竿的传送门，然后到达第i根竹竿的height[i-1]高度，向下爬行(height[i-1])/1.3秒的时间，到达第i根竹竿的底部。
2.花费footMin[i-1]的时间,到达第i-1根竹竿的底部，直接爬行，经过pos[i]-pos[i-1]秒的时间到达 第i根竹竿的底部。
得出footMin[i]的动态转移方程:
footMin[i]=Min(doorMin[i-1]+height[i-1]/1.3, footMin[i-1]+footDistance);
经历一次循环后，footMin[n-1]就是蜗牛从原点到达第n根竹竿的最短时间。
代码：
//这里从1开始，因为i=0是初始化条件。
//以n-1为终点，因为n-1的下标代表第n个竹竿
for (int i=1;i<n;i++){
int footDistance=pos[i]-pos[i-1];
//求doorMin[i]
if (height[i-1]>=door[i]){//传送过来后的高度比门高
doorMin[i]=Math.min(doorMin[i-1]+(height[i-1]-door[i])*1.0/1.3,
footMin[i-1]+footDistance+door[i]*1.0/0.7);
}else{ //传送过来后的高度比门低
doorMin[i]=Math.min(doorMin[i-1]+(door[i]-height[i-1])*1.0/0.7,
footMin[i-1]+footDistance+door[i]*1.0/0.7);
}
//求footMin[i]
footMin[i]=Math.min(doorMin[i-1]+height[i-1]*1.0/1.3,
footMin[i-1]+footDistance*1.0);
}
System.out.println(String.format("%.2f",footMin[n-1]));优化：
对于时间复杂度来说O(n)已经无法优化，
对于空间复杂度O(n)也无法优化:
但是可以减小两个数组空间的开销。
用preFoot来代替minFoot[i-1], nowFoot来替代minFoot[i];
用preDoor来代替minDoor[i-1], nowDoor来替代minDoor[i];
因为我们并不关心i-1之前的数据，可直接用迭代法代替。文章来源：https://www.toymoban.com/news/detail-426958.html
创作不易，点赞收藏加关注！！！文章来源地址https://www.toymoban.com/news/detail-426958.html
到了这里，关于2023年第十四届蓝桥杯javaB组 蜗牛解题思路（动态规划 O（n））的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
