P2495. 找终点

解题思路

与跳跃游戏的区别

乍一看本题很像 经典题型、跳跃游戏，实际上本题比后者简单很多。 在后者中，每一步的选择都可以选择小于等于当前位置数字的步数，但在本题中只有 第一步的选择是可变的。

第一步的选择范围

第一步的选择是可变的，其范围为 [1, ceil(n/2))。

题目的描述是 1 <= 第一步的步长 < n/2。

• 假设 n 为偶数，那么 len/2 是一个整数，步长取值的 右开边界 为 n//2。

例如，n = 6，那么 n/2 = 3，我们需要取到 3 的右开边界。

• 假设 n 为奇数，那么 len/2 是一个非整数，步长取值的 右开边界 为 (n+1)//2。

例如，n = 7，那么 n/2 = 3.5，我们需要取到 4 的右开边界。

n//2 和 (n+1)//2 可以用 向上取整 ceil(n/2) 来统一表示。

后续步数的固定选择

假设我们确定了第一步的步长为 step，那么第一步走完之后的位置会是 idx = 0 + step = step。

接下来每一步的选择都是固定的，我们需要讨论这些固定的步数选择能否让我们顺利走到终点（数组的最后一个位置，即索引 n-1 的位置），以及所花费的步数是多少。可以构建一个函数 check() 来判断：

整体求解过程

将 check() 放在关于 step 的循环中，每次更新全局变量 ans 即可。整体代码如下：

复杂度分析 设 n 为数组 nums 的长度（题目约定数组最多包含 100 个元素）。

• 时间复杂度：O(n²)。外层循环枚举第一步的步长 step，取值范围是 [1, ceil(n/2))，最多约 n/2 种选择；每种选择调用一次 check() 函数，函数内 idx 只会单调向数组尾部前进（每轮至少不后退，走出 n 就退出循环），所以单次 check() 最多推进 n 步，是 O(n)。两者相乘总量级为 O(n²)，n = 100 时不过几千次基本操作。
• 空间复杂度：O(1)（不计输入本身）。check() 只用了 total、idx、next_step 几个变量，主流程也只有 ans、step 等常数个变量；除了存放输入的 nums 数组（O(n)）之外没有任何额外数据结构。