(200分)- 攀登者2（Java JS Python C）

(200分)- 攀登者2（Java & JS & Python & C）

题目描述

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

地图表示为一维数组，数组的索引代表水平位置，数组的元素代表相对海拔高度。其中数组元素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。

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

登山时会消耗登山者的体力(整数)，

• 上山时，消耗相邻高度差两倍的体力
• 下山时，消耗相邻高度差一倍的体力
• 平地不消耗体力

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

例如，上图所示的山峰：

• 从索引0，走到索引1，高度差为1，需要消耗 2 * 1 = 2 的体力，
• 从索引2，走到索引3，高度差为2，需要消耗 2 * 2 = 4 的体力。
• 从索引3，走到索引4，高度差为1，需要消耗 1 * 1 = 1 的体力。

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

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

输入描述

第一行输入为地图一维数组

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

输出描述

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

用例

题目解析

本题采用核心代码模式（即无需自行处理输入数据）。

代码实现仍以ACM模式呈现，但已将输入处理与算法逻辑分离，读者只需关注算法逻辑部分。

用例1图示：

登山位置采用1-based计数，转换为数组索引（0-based）后如下：

可攀登的山峰：

• 索引9（路线：6→9→6），体力消耗=9 <13
• 索引11（路线：13→11→13），体力消耗=6 <13

此外，索引2的山峰也有两条可行路线：

• 0→2→0，体力消耗=12 <13
• 5→2→5，体力消耗=12 <13 虽然符合条件，但题目示例未列出。最终输出包含这三座山峰（索引2、9、11）。

解题思路：

1. 定位第一个地面位置（高度为0）作为起点
2. 初始化变量：
   • upCost（上山消耗）=0
   • downCost（下山消耗）=0
3. 遍历时计算高度差diff=height[i]-height[i-1]：
   • diff>0（上坡）：
     • upCost += diff×2
     • downCost += diff
   • diff<0（下坡）：
     • upCost -= diff
     • downCost -= diff×2

攀登过程中出现下坡路段是正常的。

PS：为什么攀登时会出现下坡？如图所示，若要从海拔6处攀登至海拔11的山峰，必须先越过海拔9的更高峰，这就形成了必经的下坡路段

上山时如果遇到下坡，那么相对应的，下山时，这段路程就变成了上坡路。

注意：上面diff高度差 < 0，因此 upCost += -diff，就变为了 upCost -= diff。downCost同理。

• 如果diff == 0，那么当前不消耗体力

上面 diff = heights[i] - heights[i - 1]，如果 diff < 0 以及 diff == 0时，说明位置 i 的山不是山顶。

而 diff > 0 时，位置 i 是有可能为山顶的，我们只需要检查 heights[i] > heights[i+1]即可，比如

如果确定位置 i 是山顶，则攀登此山顶的体力消耗（上山+下山）= upCost + downCost

如果此时 upCost + downCost <= 自身体力（第二行输入），那么位置 i 山顶可攀登。

另外，我们在不断向后攀登的过程中，可能会重回地面（height[i] == 0），入下图绿色框部分

此时，攀登后续山峰的最佳起点是绿色区域而非初始地面位置。因此，我们需要将 upCost 和 downCost 重置为 0，相当于从绿色区域重新开始攀登后续山峰。

以上就是基本解题思路。但这种方法存在漏洞，例如在下图中攀登索引11的山峰时，若仅考虑正向路径，最优解会是 6 → 11 → 13。

但是逆向考虑的话，会有更优解

即路径为 13 → 11 → 13

因此，我们应该正向、逆向都爬一次，这样才能保证所有山峰都能找到最优路径

upCost 和 downCost 可以合并，详细实现请参考代码注释。

攀登者的体力必须严格大于上山和下山消耗的总和，而非大于或等于。

JS算法源码

const rl = require("readline").createInterface({ input: process.stdin }); var iter = rl[Symbol.asyncIterator](); const readline = async () => (await iter.next()).value; // 输入处理 void (async function () { const heights = (await readline()).split(",").map(Number); const strength = parseInt(await readline()); console.log(getResult(heights, strength)); })(); // 算法实现（本题实际考试为核心代码模式，因此考试时只需要写出此函数实现即可） function getResult(heights, strength) { // 记录可攀登的山峰索引 const idxs = new Set(); // 正向攀登 climb(heights, strength, idxs, true); // 逆序攀登 climb(heights.reverse(), strength, idxs, false); return idxs.size; } function climb(heights, strength, idxs, direction) { // 找到第一个地面位置 let j = 0; while (j < heights.length && heights[j] != 0) { j++; } let cost = 0; // 攀登体力总消耗（包括上山，下山） // let upCost = 0; // 上山体力消耗 // let downCost = 0; // 下山体力消耗 // 开始攀登 for (let i = j + 1; i < heights.length; i++) { // 如果遇到了新的地面，则从新的地面位置重新计算攀登消耗的体力 if (heights[i] == 0) { cost = 0; // upCost = 0; // downCost = 0; continue; } const diff = heights[i] - heights[i - 1]; // diff记录高度差 if (diff > 0) { // 如果过程是上坡 cost += diff * 3; // upCost += diff * 2; // 则上山时，体力消耗 = 高度差 * 2 // downCost += diff; // 相反的下山时，体力消耗 = 高度差 * 1 // 由于 height[i] > heights[i-1]，因此如果 height[i] > heights[i+1] 的话，位置 i 就是山顶 if (i + 1 >= heights.length || heights[i] > heights[i + 1]) { // 计算攀登此山顶的上山下山消耗的体力和 if (cost < strength) { // if (upCost + downCost < strength) { // 如果不超过自身体力，则可以攀登 if (direction) { idxs.add(i); } else { idxs.add(heights.length - i - 1); // 需要注意，逆序heights数组后，我们对于的山峰位置需要反转 } } } } else if (diff < 0) { cost -= diff * 3; // upCost -= diff; // 则上山时，体力消耗 = 高度差 * 1 // downCost -= diff * 2; // 相反的下山时，体力消耗 = 高度差 * 2 // heights[i] < heights[i-1]，因此位置i不可能是山顶 } } }

Java算法源码

import java.util.Arrays; import java.util.HashSet; import java.util.Scanner; public class Main { // 输入处理 public static void main(String[] args) { Scanner sc = new Scanner(System.in); int[] heights = Arrays.stream(sc.nextLine().split(",")).mapToInt(Integer::parseInt).toArray(); int strength = Integer.parseInt(sc.nextLine()); System.out.println(getResult(heights, strength)); } // 算法实现（本题实际考试为核心代码模式，因此考试时只需要写出此函数实现即可） public static int getResult(int[] heights, int strength) { // 记录可攀登的山峰索引 HashSet<Integer> idxs = new HashSet<>(); // 正向攀登 climb(heights, strength, idxs, true); // 逆序攀登 reverse(heights); climb(heights, strength, idxs, false); return idxs.size(); } public static void climb(int[] heights, int strength, HashSet<Integer> idxs, boolean direction) { // 找到第一个地面位置 int j = 0; while (j < heights.length && heights[j] != 0) { j++; } int cost = 0; // 攀登体力总消耗（包括上山，下山） // int upCost = 0; // 上山体力消耗 // int downCost = 0; // 下山体力消耗 // 开始攀登 for (int i = j + 1; i < heights.length; i++) { // 如果遇到了新的地面，则从新的地面位置重新计算攀登消耗的体力 if (heights[i] == 0) { cost = 0; // upCost = 0; // downCost = 0; continue; } int diff = heights[i] - heights[i - 1]; // diff记录高度差 if (diff > 0) { // 如果过程是上坡 cost += diff * 3; // upCost += diff * 2; // 则上山时，体力消耗 = 高度差 * 2 // downCost += diff; // 相反的下山时，体力消耗 = 高度差 * 1 // 由于 height[i] > heights[i-1]，因此如果 height[i] > heights[i+1] 的话，位置 i 就是山顶 if (i + 1 >= heights.length || heights[i] > heights[i + 1]) { // 计算攀登此山顶的上山下山消耗的体力和 if (cost < strength) { // if (upCost + downCost <= strength) { // 如果小于自身体力，则可以攀登 if (direction) { idxs.add(i); } else { idxs.add(heights.length - i - 1); // 需要注意，逆序heights数组后，我们对于的山峰位置需要反转 } } } } else if (diff < 0) { // 如果过程是下坡 cost -= diff * 3; // upCost -= diff; // 则上山时，体力消耗 = 高度差 * 1 // downCost -= diff * 2; // 相反的下山时，体力消耗 = 高度差 * 2 // heights[i] < heights[i-1]，因此位置i不可能是山顶 } } } public static void reverse(int[] nums) { int i = 0; int j = nums.length - 1; while (i < j) { int tmp = nums[i]; nums[i] = nums[j]; nums[j] = tmp; i++; j--; } } }

Python算法源码

# 输入获取 heights = list(map(int, input().split(","))) strength = int(input()) def climb(idxs, direction): # 找到第一个地面位置 j = 0 while j < len(heights) and heights[j] != 0: j += 1 # 上山体力消耗 # upCost = 0 # 下山体力消耗 # downCost = 0 # 攀登体力总消耗（包括上山，下山） cost = 0 for i in range(j + 1, len(heights)): # 如果遇到了新的地面，则从新的地面位置重新计算攀登消耗的体力 if heights[i] == 0: cost = 0 # upCost = 0 # downCost = 0 continue # diff记录高度差 diff = heights[i] - heights[i - 1] if diff > 0: # 如果过程是上坡 cost += diff * 3 # upCost += diff * 2 # 则上山时，体力消耗 = 高度差 * 2 # downCost += diff # 相反的下山时，体力消耗 = 高度差 * 1 # 由于 height[i] > heights[i-1]，因此如果 height[i] > heights[i+1] 的话，位置 i 就是山顶 if i + 1 >= len(heights) or heights[i] > heights[i + 1]: # 计算攀登此山顶的上山下山消耗的体力和 if cost < strength: # if upCost + downCost <= strength: # 如果不超过自身体力，则可以攀登 if direction: idxs.add(i) else: idxs.add(len(heights) - i - 1) # 需要注意，逆序heights数组后，我们对于的山峰位置需要反转 elif diff < 0: # 如果过程是下坡 cost -= diff * 3 # upCost -= diff # 则上山时，体力消耗 = 高度差 * 1 # downCost -= diff * 2 # 相反的下山时，体力消耗 = 高度差 * 2 # heights[i] < heights[i-1]，因此位置i不可能是山顶 # 算法入口 def getResult(): # 记录可攀登的山峰索引 idxs = set() # 正向攀登 climb(idxs, True) # 逆序攀登 heights.reverse() climb(idxs, False) return len(idxs) # 算法调用 print(getResult())

C算法源码

#include <stdio.h> #define MAX_SIZE 100000 int canClimb[MAX_SIZE] = {0}; int canClimb_count = 0; void climb(const int heights[], int heights_size, int strength, int direction) { // 找到第一个地面位置 int j = 0; while (j < heights_size && heights[j] != 0) { j++; } int cost = 0; // 攀登体力总消耗（包括上山，下山） // int upCost = 0; // 上山体力消耗 // int downCost = 0; // 下山体力消耗 // 开始攀登 for (int i = j + 1; i < heights_size; i++) { // 如果遇到了新的地面，则从新的地面位置重新计算攀登消耗的体力 if (heights[i] == 0) { cost = 0; // upCost = 0; // downCost = 0; continue; } int diff = heights[i] - heights[i - 1]; // diff记录高度差 if (diff > 0) { // 如果过程是上坡 cost += diff * 3; // upCost += diff * 2; // 则上山时，体力消耗 = 高度差 * 2 // downCost += diff; // 相反的下山时，体力消耗 = 高度差 * 1 // 由于 height[i] > heights[i-1]，因此如果 height[i] > heights[i+1] 的话，位置 i 就是山顶 if (i + 1 >= heights_size || heights[i] > heights[i + 1]) { // 计算攀登此山顶的上山下山消耗的体力和 if (cost < strength) { // if (upCost + downCost < strength) { // 需要注意，逆序heights数组后，我们对于的山峰位置需要反转 int idx = direction ? i : heights_size - i - 1; if(!canClimb[idx]) { // 如果不超过自身体力，则可以攀登 canClimb[i] = 1; canClimb_count++; } } } } else if (diff < 0) { // 如果过程是下坡 cost -= diff * 3; // upCost -= diff; // 则上山时，体力消耗 = 高度差 * 1 // downCost -= diff * 2; // 相反的下山时，体力消耗 = 高度差 * 2 // heights[i] < heights[i-1]，因此位置i不可能是山顶 } } } void reverse(int nums[], int nums_size) { int i = 0; int j = nums_size - 1; while (i < j) { int tmp = nums[i]; nums[i] = nums[j]; nums[j] = tmp; i++; j--; } } // 算法实现（本题实际考试为核心代码模式，因此考试时只需要写出此函数实现即可） int getResult(int heights[], int heights_size, int strength) { climb(heights, heights_size, strength, 1); reverse(heights, heights_size); climb(heights, heights_size, strength, 0); return canClimb_count; } // 输入处理 int main() { int heights[MAX_SIZE]; int heights_size = 0; while (scanf("%d", &heights[heights_size++])) { if (getchar() != ',') break; } int strength; scanf("%d", &strength); printf("%d\n", getResult(heights, heights_size, strength)); return 0; }