【GESP】C++五级真题（贪心思想考点） luogu-B4051 [GESP202409 五级] 小杨的武器
GESP C++ 2024年9月五级真题，贪心思想考点，难度⭐⭐★☆☆，五级来说难度偏简单，个人认为放在四级里考也没什么问题。洛谷难度等级普及−
luogu-B4051 [GESP202409 五级] 小杨的武器
题目要求
题目描述
小杨有 $n$ 种不同的武器，他对第 $i$ 种武器的初始熟练度为 $c_i$。
小杨会依次参加 $m$ 场战斗，每场战斗小杨只能且必须选择一种武器使用，假设小杨使用了第 $i$ 种武器参加了第 $j$ 场战斗，战斗前该武器的熟练度为 $c’_i$，则战斗后小杨对该武器的熟练度会变为 $c’_i + a_j$。需要注意的是，$a_j$ 可能是正数，$0$ 或负数，这意味着小杨参加战斗后对武器的熟练度可能会提高，也可能会不变，还有可能降低。
小杨想请你编写程序帮他计算出如何选择武器才能使得 $m$ 场战斗后，自己对 $n$ 种武器的熟练度的最大值尽可能大。
输入格式
第一行包含两个正整数 $n,m$，含义如题面所示。
第二行包含 $n$ 个正整数 $c_1, c_2, \dots c_n$，代表小杨对武器的初始熟练度。
第三行包含 $m$ 个正整数 $a_1, a_2, \dots a_m$，代表每场战斗后武器熟练度的变化值。
输出格式
输出一个整数，代表 $m$ 场战斗后小杨对 $n$ 种武器的熟练度的最大值最大是多少。
输入输出样例 #1
输入 #1
1
2
3
2 2
9 9
1 -1
输出 #1
1
10
说明/提示
样例 1 解释
一种最优的选择方案为，第一场战斗小杨选择第一种武器，第二场战斗小杨选择第二种武器。
数据规模与约定
| 子任务编号 | 数据点占比 | $n$ | $m$ |
|---|---|---|---|
| $1$ | $20\%$ | $=1$ | $\leq 10^5$ |
| $2$ | $20\%$ | $\leq 10^5$ | $=2$ |
| $3$ | $60\%$ | $\leq 10^5$ | $\leq 10^5$ |
对全部的测试数据，保证 $1 \leq n, m \leq 10^5$，$-10^4 \leq c_i, a_i \leq 10^4$。
题目分析
解题思路
问题本质
有 $n$ 把武器，初始熟练度分别为 $c_i$；$m$ 场战斗，每场必须选一把武器，使用后其熟练度增加 $a_j$（可正可负）。
目标：安排每把武器的使用场次，使得 $m$ 场后所有武器熟练度的最大值尽可能大。- 关键观察
- 每场战斗只能给一把武器加 $a_j$。
- 若 $a_j>0$，显然把它加到“当前最大值”上最划算；
若 $a_j\le 0$，把它加到“当前最小值”上，对最大值无损。
因此最优策略就是： - 若只有一把武器（$n=1$），所有 $a_j$ 无论正负都必须加在这把武器上，最终结果就是 $c_1+\sum_{j=1}^m a_j$。
- 若有多把武器（$n\ge 2$），所有正 $a_j$ 全部累加到初始最大的那把武器上；负或零的 $a_j$ 可以任意分配，不影响最终最大值。
- 算法步骤
- 读入 $n,m$ 与初始熟练度数组 $c[]$。
- 若 $n=1$，则直接累加所有 $a_j$ 到 $c_1$，输出结果并结束。
- 否则找出初始最大值 $maxC=\max{c_i}$。
- 读入 $m$ 个 $a_j$，累加所有 $a_j>0$ 的值到 $maxC$。
- 输出 $maxC$。
- 复杂度
- 时间：$O(n+m)$，线性扫描。
- 空间：$O(n+m)$ ，存储输入。
示例代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <cmath>
#include <iostream>
int n_c[100005]; // 存储 n 种武器的初始熟练度
int m_a[100005]; // 存储 m 场战斗后武器熟练度的变化值
int main() {
int n, m;
std::cin >> n >> m; // 读入武器种类数 n 和战斗场数 m
for (int i = 0; i < n; i++) {
std::cin >> n_c[i]; // 读入每种武器的初始熟练度
}
for (int i = 0; i < m; i++) {
std::cin >> m_a[i]; // 读入每场战斗的熟练度变化值
}
int ans = n_c[0]; // 初始假设最大熟练度为第一种武器
if (n == 1) {
// 只有一把武器时，所有战斗只能加在这把武器上
for (int i = 0; i < m; i++) {
ans += m_a[i];
}
} else {
// 多把武器时，先找出初始熟练度最大的武器
for (int i = 1; i < n; i++) {
ans = std::max(ans, n_c[i]);
}
// 贪心：把所有正的变化值都加给当前最大熟练度的武器
for (int i = 0; i < m; i++) {
if (m_a[i] > 0) {
ans += m_a[i];
}
}
}
std::cout << ans; // 输出最终最大熟练度
return 0;
}
所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code
GESP 学习专题站：GESP WIKI
“luogu-”系列题目可在洛谷题库进行在线评测。
“bcqm-”系列题目可在编程启蒙题库进行在线评测。
欢迎加入：Java、C++、Python技术交流QQ群(982860385)，大佬免费带队，有问必答
欢迎加入：C++ GESP/CSP认证学习QQ频道，考试资源总结汇总
欢迎加入：C++ GESP/CSP学习交流QQ群(688906745)，考试认证学员交流，互帮互助
