题解

问题分析

勇者需要按环形顺序击败所有怪物，每个怪物 $i$ 有：

• 要求力量 $A_i$（必须 ≥ 此值才能击败）
• 击败后增加力量 $B_i$

目标是找到最小的初始力量 $x$，使得存在一个起点 $j$，按环形顺序击败所有怪物。

关键观察

1. 问题转化：环形序列可以拆成两段线性序列：

   • 从 $j$ 到 $n$：怪物 $j, j+1, \dots, n$
   • 从 $1$ 到 $j-1$：怪物 $1, 2, \dots, j-1$

2. 前缀和与后缀和：

   • $S[i] = B_1 + B_2 + \dots + B_i$（前缀和）
   • $s[i] = B_i + B_{i+1} + \dots + B_n$（后缀和）

3. 约束条件：

   • 对于位置 $i$，要求：$x + \text{之前获得的力量} \ge A_i$
   • 这可以转化为：$x \ge A_i - \text{之前获得的力量}$

算法思路

预处理 + 枚举起点：

预处理数组

1. $L[i]$：处理前 $i$ 个怪物时的最大约束

   $$L[i] = \max(L[i-1], A_i - S[i-1])$$

   表示处理到第 $i$ 个怪物时，初始力量需要满足的约束。

2. $R[i]$：处理后 $n-i+1$ 个怪物时的最大约束（从右往左）

   $$R[i] = \max(R[i+1] - B_i, A_i)$$

   表示从位置 $i$ 开始往右打到最后时，在位置 $i$ 需要的力量。

计算答案

对于每个可能的起点 $i$：

• 先打 $i \to n$，需要力量 $R[i]$
• 再打 $1 \to i-1$，此时已有力量 $R[i] + s[i]$，需要满足 $L[i-1]$ 的约束
• 所以初始力量需要：$\max(R[i], L[i-1] - s[i])$

取所有起点中的最小值。

核心代码逻辑

// 预处理后缀和
for (int i = n; i >= 1; --i) {
    s[i] = s[i + 1] + b[i];
}

// 预处理前缀和  
for (int i = 1; i <= n; ++i) {
    S[i] = S[i - 1] + b[i];
}

// 从左往右处理约束
for (int i = 1; i <= n; ++i) {
    L[i] = max(L[i - 1], a[i] - S[i - 1]);
}

// 从右往左处理约束
for (int i = n; i >= 1; --i) {
    R[i] = max(R[i + 1] - b[i], a[i]);
}

// 枚举起点找最小值
ll ans = 1e18;
for (int i = 1; i <= n; ++i) {
    ll res = max(R[i], L[i - 1] - s[i]);
    ans = min(ans, res);
}

复杂度分析

• 预处理：$O(n)$ 计算前缀和、后缀和、$L$ 数组、$R$ 数组
• 枚举起点：$O(n)$
• 总复杂度：$O(n)$

算法步骤

1. 读入 $n, A, B$
2. 计算前缀和 $S$ 和后缀和 $s$
3. 从左到右计算 $L$ 数组
4. 从右到左计算 $R$ 数组
5. 枚举所有起点，计算所需初始力量
6. 输出最小值

算法标签

• 前缀和/后缀和
• 动态规划
• 环形数组处理
• 贪心思想
• 最优化问题