蓝桥杯-蜗牛[Java]_蜗牛蓝桥杯

目录

问题描述:

输入格式:

输出格式:

样例输入:

样例输出:

样例说明:

评测用例规模与约定:

分析:

代码:

问题描述:

这天，一只蜗牛来到了二维坐标系的原点。 在 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)，请计算蜗牛最少需要多少秒才能到达目的地。

输入格式:

输入共1+n行，第一行为一个正整数n；
第二行为n个正整数x1,x2, . . . ,xn；
后面n−1行，每行两个正整数ai,bi+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⁹ 。

分析:

• 蜗牛到达竹竿的方式有两种:1.通过传送门移动，2.通过竹竿底部平移。
• 所以，我们用time_transmit来表示通过传送门来移动的时间，用time_glide表示从竹竿底部平移的时间。
• 从第2根竹竿开始到第n-1根竹竿结束，存在两个传送门，我们用transmit_ai表示入口，transmit_bi表示出口。

• 要到达第n根竹竿的底部,存在的情况如下:

• 1.通过n-1的传送门到n的传送门,然后向下到底部

• 2.通过n-1的底部直接到n底部;

• 通过height = ai - bi-1 来计算出两道传送门的高度差,来计算通过传送门移动的时间 假设i=2,则表示的是第1根到第2根所花费的时间

• ①.如果是正数,说明需要向上爬到传送门 :time_transmit = height / 0.7

• ②.如果是负数,说明需要向下爬到传送门 :time_transmit = -height / 1.3

• 如果是从i-1的传送门到i的底部的时间

• ③.time_glide = bi / 1.3 + (x_place[i] - x_place[i-1])

代码:

import java.util.Scanner;
 
 
public class Main {
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();//竹杆数
        int[] x_place = new int[n];//竹竿的横坐标位置
        for(int i = 0;i < n;i++) {
            x_place[i] = in.nextInt();//输入n行竹竿的横坐标
        }
        int[] transmit_ai = new int[n];//ai,n对应的就是第n根竹竿
        int[] transmit_bi = new int[n];//bi,n对应的就是第n+1根竹竿
        for(int i = 0;i < n-1;i++) {
            transmit_ai[i] = in.nextInt();//ai
            transmit_bi[i] = in.nextInt();//bi
        }
        in.close();
 
        double[] time_transmit = new double[n];//从原点到第n根竹竿传送门的最短时间
        double[] time_glide = new double[n];//从原点到第n根竹竿底部的最短时间
 
        time_transmit[0] = x_place[0] + transmit_ai[0] / 0.7;//走到第一根竹竿的传送门的时间
        time_glide[0] = x_place[0];//走到第一根竹竿的时间
 
        for(int i = 1;i < n;i++) {
            int distance = x_place[i] - x_place[i-1];
            int height = transmit_ai[i] - transmit_bi[i-1];
            if(height > 0) {
                time_transmit[i] = Math.min(time_transmit[i-1] + height / 0.7,time_glide[i-1] + distance + transmit_ai[i]/0.7);
            } else {
                time_transmit[i] = Math.min(time_transmit[i-1] + -height / 1.3,time_glide[i-1] + distance + transmit_ai[i]/0.7);
            }
            time_glide[i] = Math.min(time_transmit[i-1] + transmit_bi[i-1] / 1.3,time_glide[i-1] + distance);
        }
        System.out.println(String.format("%.2f",time_glide[n-1]));
    }
}