📝 题目大意

有 $N$ 个国家，初始持有第 $i$ 国的货币 $A_i$ 单位。对于每个 $i$（$1 \le i \le N-1$），可以花费 $S_i$ 单位第 $i$ 国货币兑换 $T_i$ 单位第 $i+1$ 国货币，且 $T_i \le S_i$。可以进行任意次操作，求最终能获得的第 $N$ 国货币的最大数量。

💡 解题思路

1. 题目分析：

   • $N \le 2 \times 10^5$，$A_i, S_i, T_i \le 10^9$，数据范围大，需要 $O(N)$ 解法并用 long long 存储。
   • 兑换只能从 $i$ 到 $i+1$，单向不可逆，且 $T_i \le S_i$（兑换不会增值）。
   • 所有货币最终必须经过中间国家才能抵达第 $N$ 国，不存在向后兑换的路径。

2. 算法推导：

   • 由于兑换是单向的（$i \to i+1$），留在第 $i$ 国的货币无法再向前传递，因此最优策略是贪心地将所有能兑换的货币尽可能向前推进。
   • 对于每个 $i$，若 $A_i \ge S_i$，则可以进行 $cnt = \lfloor A_i / S_i \rfloor$ 次兑换：$A_i$ 减少 $cnt \times S_i$，$A_{i+1}$ 增加 $cnt \times T_i$。
   • 依次处理 $i = 1, 2, \dots, N-1$，最终 $A_N$ 即为答案。
   • 没有选择分支，不需要 DP 或回溯，直接模拟即可。

3. 边界与细节：

   • 当 $A_i < S_i$ 时，无法兑换，该国的剩余货币被"浪费"（无法到达第 $N$ 国），直接跳过。
   • 使用 long long 避免溢出：$A_i$ 最大 $10^9$，累计兑换后可能超过 $2^{31}-1$。
   • 下标从 $1$ 开始，与题目描述保持一致，避免混淆。

⏱️ 复杂度分析

• 时间复杂度：$O(N)$，只需一次遍历。
• 空间复杂度：$O(N)$，存储 $A$、$S$、$T$ 三个数组。

💻 标准代码 (C++)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int N;
    cin >> N;
    
    vector<long long> A(N + 1);          // 1-indexed，各国货币持有量
    for (int i = 1; i <= N; i++) {
        cin >> A[i];
    }
    
    vector<long long> S(N), T(N);        // S[i], T[i] 对应 i -> i+1 的兑换参数
    for (int i = 1; i <= N - 1; i++) {
        cin >> S[i] >> T[i];
    }
    
    // 贪心：从第1国到第N-1国，依次将货币尽可能向前兑换
    for (int i = 1; i <= N - 1; i++) {
        if (A[i] >= S[i]) {              // 足够支付一次兑换
            long long cnt = A[i] / S[i]; // 计算最多可兑换次数
            A[i] -= cnt * S[i];          // 扣除付出的货币
            A[i + 1] += cnt * T[i];      // 获得目标国货币
        }
    }
    
    cout << A[N] << endl;                // 最终第N国的货币数量即为答案
    
    return 0;
}