小杨的武器 题解

题目分析

小杨有 $n$ 种武器，每种武器有初始熟练度 $c_i$。他必须依次参加 $m$ 场战斗，每场战斗选择一种武器使用，使用后该武器的熟练度增加 $a_j$（$a_j$ 可能为正、负或零）。

目标：最大化 $m$ 场战斗后所有武器熟练度的最大值。

通俗理解：我们要安排每场战斗用哪种武器，使得最终熟练度最高的那个武器的熟练度尽可能高。至于其他武器的熟练度是多少，我们并不关心，只要它们不超过这个最大值即可。

解题思路

关键点在于：我们可以自由决定每场战斗由哪个武器承担。如果能将“好”的战斗（$a_j>0$）全部集中给一个武器，而将“坏”的战斗（$a_j \le 0$）交给其他武器去承担，那么主力武器的熟练度就不会受到坏战斗的影响，从而获得最大的成长。

但这里有两种情况需要讨论：

1. 只有一种武器（$n = 1$）

此时别无选择，所有战斗都必须由这唯一的武器承担。无论 $a_j$ 是正是负，都得累加上去。最终熟练度为：

2. 有多种武器（$n \ge 2$）

我们可以采用如下策略：

• 选择一个初始熟练度最大的武器作为“主力”。
• 将所有 $a_j>0$ 的战斗分配给主力武器，使其熟练度不断增加。
• 将所有 $a_j \le 0$ 的战斗分配给其他任意一个武器（比如初始熟练度最小的那个），让它们承受负面影响。

这样，主力武器的最终熟练度为：

由于其他武器初始就不超过 $\max(c_i)$，再承担非正收益后只会更低，因此主力武器的熟练度就是最终所有武器中的最大值。显然这个值是能达到的最大值——因为任何武器承担非正收益都会让它的熟练度减少或不变，我们没必要让主力去承担这些损失。

算法说明

1. 读入 $n, m$。
2. 读入 $n$ 个初始熟练度 $c_i$，并记录最大值 $c_{\max}$。
3. 读入 $m$ 个变化值 $a_j$。
4. 初始化答案 $\text{ans} = c_{\max}$。
5. 遍历每个 $a_j$：
   • 如果 $n == 1$ 或 $a_j>0$，则 $\text{ans} \leftarrow \text{ans} + a_j$。
6. 输出 $\text{ans}$。

时间复杂度分析

• 读入 $c_i$ 并求最大值：$O(n)$。
• 读入 $a_j$ 并进行累加判断：$O(m)$。
• 总时间复杂度：$O(n+m)$，可以轻松通过 $n, m \le 10^5$ 的数据规模。
• 空间复杂度：$O(n+m)$ 或 $O(1)$（若边读边处理），参考代码使用了数组存储，空间也在题目限制内。

参考代码及解释

cpp
复制
1#include <bits/stdc++.h>
2using namespace std;
3
4const int N = 100010;
5int a[N], c[N];
6
7int main() {
8    int n, m;
9    cin >> n >> m;
10
11    // 读入初始熟练度，并记录最大值
12    int mx = -10000;               // 由于 c_i 可能为负，初始设一个较小值
13    for (int i = 1; i <= n; ++i) {
14        cin >> c[i];
15        mx = max(mx, c[i]);
16    }
17
18    // 读入每场战斗的变化值
19    for (int i = 1; i <= m; ++i) {
20        cin >> a[i];
21    }
22
23    // 计算答案
24    for (int i = 1; i <= m; ++i) {
25        if (n == 1 || a[i] > 0) {  // 唯一武器或正收益战斗才累加
26            mx += a[i];
27        }
28    }
29
30    cout << mx << "\n";
31    return 0;
32}

代码说明：

• 用 mx 同时充当“初始熟练度最大值”和“最终答案”的角色。
• 第一个循环求 $c_i$ 的最大值。
• 第二个循环读入所有 $a_i$（其实可以边读边处理，省去数组）。
• 第三个循环判断条件 n == 1 || a[i] > 0：
  • n == 1：唯一武器，无论 $a_i$ 正负都必须加；
  • a[i] > 0：多武器时，只累加正收益战斗。
• 最后输出 mx 即为答案。

思考拓展

如果题目要求最小化熟练度的最大值，或者要求所有武器熟练度尽可能平均，策略会完全不同。但本题只关心“最大值尽可能大”，因此集中资源给一个武器的贪心策略是最优且高效的。这种“扬长避短”的思想在竞赛中非常常见，希望对大家有所启发。