📝 题目大意

有 $N$ 个房间排成一条直线，初始在房间 $1$，持有时间 $T$。从房间 $i$ 移动到 $i+1$ 需要消耗 $A_i$ 的时间，移动后若时间 $\le 0$ 则无法移动。有 $M$ 个奖励房间，到达房间 $X_i$ 时获得 $Y_i$ 的额外时间。问能否到达房间 $N$。

💡 解题思路

1. 题目分析：$N \le 10^5$，只能 $O(N)$ 或 $O(N \log N)$ 解决。$T, A_i, Y_i$ 均可达 $10^9$，中途累加可能超过 $2^{31}-1$，必须使用 long long。
2. 算法推导：
   • 用一个数组 bonus 记录每个房间的奖励值（没有奖励的房间为 $0$）。
   • 从房间 $1$ 出发，维护当前剩余时间 time（初始为 $T$），依次尝试移动到房间 $2, 3, \ldots, N$。
   • 对于每次移动（从房间 $i$ 到 $i+1$）：
     • 若 time <= A[i-1]，说明时间不足以移动到下一房间，无法到达终点，直接输出 No。
     • 否则，扣除移动消耗 time -= A[i-1]，然后加上目的地房间的奖励 time += bonus[i+1]。
   • 若循环顺利结束（即成功到达房间 $N$），输出 Yes。
   • 为什么奖励房间是 bonus[i+1]？因为循环中 $i$ 代表当前所在房间编号，bonus[i+1] 即为到达房间 $i+1$ 时应获得的奖励。
3. 边界与细节：
   • 移动条件为 time <= A[i-1]（严格大于才能移动），与题目"移动后时间变为 $0$ 或更少则无法移动"一致。
   • $M$ 可能为 $0$，此时 bonus 数组全为 $0$，只需判断能否靠初始时间走完全程。
   • 奖励房间按 $X_i$ 严格递增给出，且 $X_i < N$，故 bonus[N] 恒为 $0$，不影响最终结果。
   • 必须使用 64 位整数存储时间，否则 $T$ 和 $Y_i$ 累加可能溢出。

⏱️ 复杂度分析

• 时间复杂度：$O(N + M)$，遍历 $N-1$ 次移动，加上 $M$ 次奖励读入。
• 空间复杂度：$O(N)$，用于存储 $A$ 数组和 bonus 数组。

💻 标准代码 (C++)

#include<bits/stdc++.h>
using namespace std;
int main() {
    int N, M, T;
    cin >> N >> M >> T;
    vector<int> A(N - 1);          // A[i] 表示从房间 i+1 到 i+2 的移动消耗
    for (int i = 0; i < N - 1; i++) cin >> A[i];
    vector<int> bonus(N + 1, 0);   // bonus[x] = 到达房间 x 时获得的时间奖励
    for (int i = 0; i < M; i++) {
        int X, Y;
        cin >> X >> Y;
        bonus[X] = Y;              // 房间 X 可获得 Y 的奖励时间
    }
    long long time = T;            // 64 位存储当前剩余时间，防止溢出
    bool canReach = true;          // 标记能否到达终点
    for (int i = 1; i < N; i++) {  // 从房间 1 出发，依次尝试移动到房间 2,3,...,N
        if (time <= A[i - 1]) {    // 剩余时间不足以移动到下一房间
            canReach = false;
            break;
        }
        time -= A[i - 1];          // 扣除移动消耗
        time += bonus[i + 1];      // 到达房间 i+1，领取奖励（若有）
    }
    cout << (canReach ? "Yes" : "No");
    return 0;
}