问题本质

在环形路径上找到起点，使得机器人以最小初始灵活度 $a$ 能完成一圈，每次跳跃后灵活度 $+1$。

核心思路

关键转化

从起点 $s$ 开始，第 $j$ 次跳跃需要满足：

即：

因此对于起点 $s$，最小初始灵活度为：

目标：找到使 $a_s$ 最小的 $s$。

算法步骤

1. 生成距离数组 $d[0..n-1]$

   • $f=1$：直接读入
   • $f=2$：按递推公式生成

2. 构造需求数组

   • $need[i] = d[i] - i$（$i = 0$ 到 $n-1$）
   • 复制：$need[n+i] = need[i]$（处理环形）

3. 滑动窗口求最大值

   • 使用单调队列维护长度为 $n$ 的窗口
   • 对每个起点 $i$，$max\_need$ = 窗口内最大值
   • $a_i = max\_need + i$

4. 选择最优解

   • 找到最小的 $a_i$ 及对应的 $s = i+1$

复杂度

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

实现要点

• 使用双端队列实现单调队列
• 注意索引从0还是1开始
• 模运算处理环形

这种解法将环形问题转化为线性问题，利用滑动窗口高效求解。