AlgoMooc
← 返回题库

P2532. 攀登者1

简单通过率 57% · 提交 142 · 通过 81
模拟枚举

小慕正在研究一张特殊的地图,这张地图用表示,数组的代表水平位置,数组的高度代表相对海拔高度。其中数组元素 `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`。 一个山脉可能有多座山峰(高度大于相邻位置的高度,或在地图边界且高度大于相邻的高度)。

                4

              +---+
              |   |
              |   | 3                       3
              |   |
              |   +---+                   +---+
              |       |                   |   |
            2 |       |                 2 |   |     2
              |       |                   |   |
          +---+       |               +---+   |   +---+
          |           |               |       |   |   |
        1 |           | 1           1 |       | 1 |   | 1
          |           |               |       |   |   |
      +---+           +---+       +---+       +---+   +---+
      |                   |       |                       |
    0 |                   | 0   0 |                       | 0
      |                   |       |                       |
  +---+                   +-------+                       +---+

    0   1   2   3   4   5   6   7   8   9  10  11  12  13  14

小慕在登山时会消耗体力(整数),上山时,消耗两倍的体力,下坡时消耗相邻高度差一倍的体力,平地不消耗体力,体力消耗到零时会有生命危险。 例如,上图所示的山峰:从 `0`,走到索引 `1`,高度差为 `1`,需要消耗 `2*1=2` 的体力;从索引 `2` 高度 `2`走到高度 `4` 索引 `3` 需要消耗 `2*2=4` 的体力;从索引 `3` 走到索引 `4` 则消耗 `1*1=1` 的体力。 小慕想知道这张地图中有多少座山峰?

提示:带虚线的词点一下有通俗解释。

输入描述

第一行输入一个长度为N的数组,表示地图。

输出描述

输出一个数字,地图中的山峰数量

示例

示例 1

输入

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

输出

3

时间限制 1000 ms · 内存限制 128 MB

看不懂题目?点开图解(训练营专属)

登录后查看题目图解

题目图解为训练营学员专属内容,请先登录。

微信扫码登录还不是训练营学员?了解训练营 →
写完代码点「提交」,将对全部测试用例判题。