原题链接：蓝桥杯2023年第十四届省赛真题-蜗牛
解题思路:
注意事项:
参考代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 | import java.util.Map;import java.util.Scanner;/** * 这天，一只蜗牛来到了二维坐标系的原点。 * 在 x 轴上长有 n 根竹竿。它们平行于 y 轴，底部纵坐标为 0，横坐标分别为 x1, x2, ..., xn。 * 竹竿的高度均为无限高，宽度可忽略。蜗牛想要从原点走到第 n 个竹竿的底部也就是坐标 (xn, 0)。 * 它只能在 x 轴上或者竹竿上爬行，在 x 轴上爬行速度为 1 单位每秒； * 由于受到引力影响，蜗牛在竹竿上向上和向下爬行的速度分别为 0.7 单位每秒和 1.3 单位每秒。 * 为了快速到达目的地，它施展了魔法，在第 i 和 i + 1 根竹竿之间建立了传送门（0 < i < n）， * 如果蜗牛位于第 i 根竹竿的高度为 ai 的位置 (xi , ai)，就可以瞬间到达第 i + 1 根竹竿的高度为 bi+1 的位置 (xi+1, bi+1)， * 请计算蜗牛最少需要多少秒才能到达目的地。 */public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[] x = new int[n]; // 表示的是第i个竹竿和前一个的距离 for (int i = 0; i < n; i++) { x[i] = sc.nextInt(); } if (n == 1){ System.out.printf("%.2f", (double)x[0]); return; } int[] a = new int[n - 1]; int[] b = new int[n - 1]; // 实际上是最后一根不需要魔法，顶多只会爬下来 for (int i = 0; i < n - 1; i++) { a[i] = sc.nextInt(); b[i] = sc.nextInt(); } double vX = 1, vUp = 0.7, vDown = 1.3; double[][] dp = new double[n][2]; // 0表示到达y0，1表示到达魔法该到达的起始位置。 // 第一个竹竿无论用不用魔法，都是x[0] / vX dp[0][0] = x[0] / vX; dp[0][1] = x[0] / vX + a[0] / vUp; for (int i = 1; i < n - 1; i++) { // 这个表示到达第i根竹竿最低端所需的时间 int dis = x[i] - x[i - 1]; // 底端的值要么是前一个底端的加距离，要么是前一个的魔法位置爬下来之后的时间。 // 实际上使用了魔法的话，就相当于不走x轴了，直接从魔法位置爬下来。 dp[i][0] = Math.min(dp[i - 1][0] + dis / vX,dp[i-1][1] + b[i - 1] / vDown);// System.out.println(dp[i][0]); // 如果是魔法位置的话，实际上就是本身的底端爬到对应的位置，或者是 // 前一个的魔法位置爬到自己所对应的魔法位置的时间 double timeGap = 0; // 如果前一个的位置的魔法结果要比自己应该在的魔法初始位置要矮的话，那么要往上爬 if (a[i] > b[i - 1]){ timeGap = (a[i] - b[i - 1]) / vUp; } else { timeGap = (b[i - 1] - a[i]) / vDown; } dp[i][1] = Math.min(dp[i][0] + a[i] / vUp, dp[i-1][1] + timeGap);// System.out.println(dp[i][1]); } // 最后一步是特例，提出来判断 dp[n - 1][0] = Math.min(dp[n - 2][0] + (x[n - 1] - x[n - 2]) / vX, dp[n - 2][1] + b[n - 2] / vDown); dp[n - 1][1] = Math.min(dp[n - 1][0], dp[n - 2][1] + b[n - 2] / vDown); System.out.printf("%.2f", dp[n - 1][0]); }} |
9.9 分
3 人评分
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：
一点编程也不会写的：零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码？手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程
发表评论 取消回复