ABC265B Explore

题目分析

Takahashi 要从房间 $1$ 依次走到房间 $N$，每一步（从 $i$ 到 $i+1$）需要花费时间 $A_i$。

他一开始有时间限制 $T$。如果他走到某些特殊房间（称为奖励房间 $X_i$），时间会增加 $Y_i$。

移动规则是：

• 每次移动前必须保证当前剩余时间 > A[i]；
• 否则无法继续移动；
• 奖励只能在到达对应房间时才生效。

目标是判断他是否能走到房间 $N$。

---

解题思路

• 我们从房间 $1$ 出发，一步步向房间 $N$ 移动；
• 每次移动消耗时间，如果当前时间不足则直接输出 No；
• 如果到了奖励房间，就加上对应的奖励时间；
• 如果顺利移动到房间 $N$，输出 Yes。

---

实现步骤

• 定义数组 A[100005] 存每次移动所需时间；
• 用一个数组存储每个奖励房间的加时时间；
  • 例如定义一个数组 B[100005]，执行 B[X] += Y
• 用变量 T 表示当前剩余时间；

• 遍历 i = 1 到 N-1：

  • 如果 i 是奖励房间，令 T += B[i]；
  • 其次令 T -= A[i] 减去穿越花费的时间；
  • 如果 T <= 0，输出 No。并结束程序；

• 循环结束后输出 Yes。

• 根据数据范围需要 long long。

---

复杂度分析

• 时间复杂度：$O(N + M)$
• 遍历房间 $O(N)$；
• 奖励房间用数组预处理 $O(M)$；
• 空间复杂度：$O(M)$，用于存储奖励信息。

---

总结

• 本题关键是模拟 Takahashi 的移动过程；
• 奖励时间只有在到达特定房间时才加上；
• 注意每一步移动之前必须检查剩余时间是否足够；
• 题目中数据较大，注意数组下标处理，尽量避免边界错误。