#616. 探险家的跳跃计划

探险家的跳跃计划

探险家的跳跃计划

故事背景

一位探险家正在穿越一片由浮岛组成的海域。浮岛排成了一条直线,每座浮岛上都写着一个非负整数,表示从这座浮岛出发,最多可以向前跳跃多少步。

探险家从第 1 座浮岛出发(下标从 1 开始编号),每次可以选择向前跳 1 步、2 步,直到当前浮岛写明的最大步数为止。探险家想知道,自己是否有办法跳到最后一座浮岛上。

题目描述

给定一个长度为 nn 的非负整数数组,其中第 ii 个元素表示从位置 ii 最多可以向前跳跃的步数。你一开始位于下标为 1 的位置(即数组的第一个元素处)。

每次跳跃,你可以选择向前移动 1 到当前允许的最大步数之间的任意整数步。判断是否存在一种跳跃方式,使你能够到达最后一个位置。

输入格式

  • 第一行包含一个整数 nn,表示浮岛的数量。
  • 第二行包含 nn 个非负整数,第 ii 个数表示从第 ii 座浮岛最多可以向前跳跃的步数。

输出格式

  • 如果可以到达最后一座浮岛,输出 YES
  • 否则输出 NO

输入输出样例 #1

输入 #1

5
2 3 1 1 4

输出 #1

YES

样例解释 #1

一种可行跳法是:从位置 1 跳到位置 2,再从位置 2 跳到位置 5。

输入输出样例 #2

输入 #2

5
3 2 1 0 4

输出 #2

NO

样例解释 #2

无论如何,都无法跳过位置 4 处的“0”,因此到达不了最后一座浮岛。

说明/提示

  • 对于所有测试数据,保证 1n2×1051 \le n \le 2 \times 10^5
  • 数组中的元素为不超过 10910^9 的非负整数。