华为OD机试 - 攀登者2（Java 2024 C卷 200分）

迷南。 2024-04-29 19:13 122阅读 0赞

![在这里插入图片描述][986dcebce006483fb6846cb29a3928a7.gif_pic_center]

> 华为OD机试 2024C卷题库疯狂收录中，刷题[**点这里**][Link 1]

### 专栏导读 ###

本专栏收录于[《华为OD机试（JAVA）真题（A卷+B卷+C卷）》][OD_JAVA_A_B_C]。

**刷的越多，抽中的概率越大**，每一题都有详细的答题思路、详细的代码注释、样例测试，发现新题目，随时更新，全天CSDN在线答疑。

### 一、题目描述 ###

攀登者喜欢寻找各种地图，并且尝试攀登到最高的山峰。

地图表示为一维数组，数组的索引代表水平位置，数组的元素代表相对海拔高度。其中数组元素0代表地面。

例如：\[0,1,2,4,3,1,0,0,1,2,3,1,2,1,0\]，代表如下图所示的地图，地图中有两个山脉位置分别为 1,2,3,4,5 和 8,9,10,11,12,13，最高峰高度分别为 4,3。最高峰位置分别为3,10。

一个山脉可能有多座山峰(高度大于相邻位置的高度，或在地图边界且高度大于相邻的高度)。

![在这里插入图片描述][67912241659b47d48297f76d8f16eefb.png_pic_center]

登山时，会消耗登山者的体力（整数），

1.  上山时，消耗相邻高度差两倍的体力；
2.  下山时，消耗相邻高度差一倍的体力；
3.  平底不消耗体力；

登山者体力消耗到0时会有生命危险。

例如，上图所示的山峰：

1.  从索引0到索引1，消耗2体力；
2.  从索引1到索引2，消耗2体力；
3.  从索引2到索引3，消耗4体力

登山者想要评估一张地图内有多少座山峰可以进行攀登，且可以安全返回地面，且无生命危险。

例如上图中的数组，有3个不同的山峰，登山位置在3的山峰可以从位置0或者位置6开始，从位置0登到山顶需要消耗体力 1 \* 2 + 1 \* 2 + 2 \* 2 = 8，从山顶返回地面需要消耗体力 2 \* 1 + 1 \* 1 + 1 \* 1 = 4体力，按照登山路线0 - 3 - 0需要消耗体力12。攀登者至少需要12以上的体力才能安全返回。

### 二、输入描述 ###

第一行输入一组数字，逗号隔开

第二行输入攀登者的体力。

### 三、输出描述 ###

确保可以安全返回地面，且无生命危险的前提下，地图中有多少山峰可以攀登。

### 四、解题思路 ###

**核心思想：**

1.  计算每座山所消费的体力
2.  找出体力可以满足登完哪几座连续的山

--------------------

1.  只能从地面0处开始攀登，所以从0开始遍历
2.  体力可以攀登下一座山峰，并成功回到地面0时体力大于0
3.  循环往复，找到最多可以爬几座山

没说一定要从左往右爬山，倒着爬也可以。

### 五、Java算法源码 ###

public class Test07 {
        
        public static void main(String[] args) {
        
            Scanner sc = new Scanner(System.in);
            /**
             * 1. 只能从地面0处开始攀登，所以从0开始遍历
             * 2. 体力可以攀登下一座山峰，并成功回到地面0时体力大于0
             * 3. 循环往复，找到最多可以爬几座山
             *
             * 1. 计算每座山所消费的体力
             * 2. 找出体力可以满足登完哪几座连续的山
             *
             * 注意可以逆向攀登
             */
            int[] arr = Arrays.stream(sc.nextLine().split(",")).mapToInt(Integer::parseInt).toArray();
            int powerAll = Integer.valueOf(sc.nextLine());
            // 计算最多可以爬几座山
            getMaxMountain(arr, powerAll);
    
            // 将数组元素反转
            reverseArr(arr);
            for (int i = 0; i < arr.length; i++) {
        
                System.out.print(arr[i]+",");
            }
            // 计算最多可以爬几座山
            getMaxMountain(arr, powerAll);
        }
    
        // 将数组元素反转
        private static void reverseArr(int[] arr){
        
            int start = 0;
            int end = arr.length - 1;
            while (start < end) {
        
                // 交换起始和末尾元素的值
                int temp = arr[start];
                arr[start] = arr[end];
                arr[end] = temp;
                start++;
                end--;
            }
        }
    
        // 当前体力下最多能爬多少座山
        static int max = 0;
        private static void getMaxMountain(int[] arr, int powerAll){
        
            // 山峰开始的标识
            boolean mountainFlag = false;
            // 从0到0开始的表示，中间可能爬若干个山
            boolean flag = false;
    
            // 一次从0到0要爬几座山
            int mountainSum = 0;
    
            // 从0到0消耗的体力
            int power = 0;
            // 上一次从0到0消耗的体力
            int prePower = 0;
            // 消耗体力 + 一次完整的0到0有几座山
            List<String> powerList = new ArrayList<>();
            for (int i = 0; i < arr.length; i++) {
        
                int cur = arr[i];
                // 最后一个，如果是0，表示一次完整的0到0的登山
                if (i == arr.length - 1 && cur == 0) {
        
                    powerList.add(power + "+" + mountainSum);
                    break;
                }
                int next = arr[i + 1];
    
                // 如果当前数比下一个数小，就表示一个山峰的开始
                if (mountainFlag == false && cur < next) {
        
                    mountainFlag = true;
                }
    
                // 直至当前数比下一个数大，就表示一个山峰的结束
                if (mountainFlag == true && cur > next) {
        
                    mountainFlag = false;
                    mountainSum++;
                }
    
                // 从平地出发，如果当前数比下一个数小，就表示一个山峰的开始
                if (flag == false && cur == 0 && cur < next) {
        
                    flag = true;
    
                    // 0到0重新开始，上一次完整0到0所消耗的体力
                    if(power != 0){
        
                        powerList.add(power + "+" + mountainSum);
                        power = 0;
                    }
    
                    power += (next - cur) * 2;
                    continue;
                }
    
                // 到达下一个平地，表示爬完一座山
                if (flag == true) {
        
                    // 从0到0一次完整的爬山
                    if (cur == 0) {
        
                        flag = false;
    
                        powerList.add(power + "+" + mountainSum);
    
                        power = 0;
                        mountainSum = 0;
                        // 又一次从0到0爬山的开始
                        if (cur < next) {
        
                            flag = true;
                        }
                    }
    
                    // 上山消耗相邻高度两倍体力
                    if (next > cur) {
        
                        power += (next - cur) * 2;
                    } else if (next < cur) {
        // 下山消耗相邻高度一倍体力
                        power += cur - next;
                    }
                }
            }
            System.out.println(powerList);
    
            // 连续从0到0爬山消耗的体力
            int powerMountain = 0;
            // 连续从0到0爬了几座山
            int mountain = 0;
    
            // 上一次连续从0到0爬了几座山
            int preMountain = 0;
    
    
            /**
             * 消耗体力 + 有几座山，12+1,12+2
             */
            for (int i = 0; i < powerList.size(); i++) {
        
                String cur = powerList.get(i);
                String[] curArr = cur.split("\\+");
                powerMountain += Integer.valueOf(curArr[0]);
                // 体力不够了
                if (powerMountain >= powerAll) {
        
                    // 上一次连续从0到0爬了几座山
                    max = Math.max(max, preMountain);
                    preMountain = 0;
    
                    // 连续从0到0爬了几座山
                    mountain = 0;
                    mountain += Integer.valueOf(curArr[1]);
                    max = Math.max(max, mountain);
                    powerMountain = 0;
                    powerMountain += Integer.valueOf(curArr[0]);
                } else {
        // 还能继续尝试爬下一座
                    // 连续从0到0爬了几座山
                    mountain += Integer.valueOf(curArr[1]);
                    preMountain += Integer.valueOf(curArr[1]);
                    max = Math.max(max, mountain);
                }
            }
    
            System.out.println(max);
        }
    }

### 六、效果展示 ###

#### 1、输入 ####

0,1,4,3,1,0,0,1,2,3,1,2,1,0,0,1,2,1,2,1,0  
22

#### 2、输出 ####

#### 3、说明 ####

![在这里插入图片描述][a5b4f9ef985d4672abc998071de9f1d5.bmp_pic_center]

?下一篇：[华为OD机试 - 简易内存池 - 逻辑分析（Java 2024 C卷 200分）][OD_ - _ - _Java 2024 C_ 200]

?本文收录于，[华为OD机试（JAVA）真题（A卷+B卷+C卷）][OD_JAVA_A_B_C]

**刷的越多，抽中的概率越大**，每一题都有详细的答题思路、详细的代码注释、样例测试，发现新题目，随时更新，全天CSDN在线答疑。

![在这里插入图片描述][8dbe8dd8723c4636af5926ccf1c511b0.gif_pic_center]

[986dcebce006483fb6846cb29a3928a7.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/29/f89f78f192e94b469409b1d934677094.gif
[Link 1]: https://blog.csdn.net/guorui_java/article/details/132683473
[OD_JAVA_A_B_C]: https://blog.csdn.net/guorui_java/category_12293298.html
[67912241659b47d48297f76d8f16eefb.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/29/538bab92e4314649b15335fb132ab772.png
[a5b4f9ef985d4672abc998071de9f1d5.bmp_pic_center]: https://img-blog.csdnimg.cn/direct/a5b4f9ef985d4672abc998071de9f1d5.bmp#pic_center
[OD_ - _ - _Java 2024 C_ 200]: https://blog.csdn.net/guorui_java/article/details/132197477
[8dbe8dd8723c4636af5926ccf1c511b0.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/29/acf34fde722b44d795f5474fb2a8f131.gif