2023年第十四届蓝桥杯javaB组 蜗牛解题思路（动态规划 O（n））

 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之前的数据，可直接用迭代法代替。

创作不易，点赞收藏加关注！！！