【GESP】C++四级真题 luogu-B4006 [GESP202406 四级] 宝箱
GESP C++四级2024年6月真题。本题主要考察排序、前缀和和滑动窗口思想。暴力难度不大，滑动窗口需要点思想，整体难度⭐⭐★☆☆。本题在洛谷评定为普及-。
luogu-B4006 [GESP202406 四级] 宝箱
题目要求
题目描述
小杨发现了 $n$ 个宝箱，其中第 $i$ 个宝箱的价值是 $a_i$。
小杨可以选择一些宝箱放入背包并带走，但是小杨的背包比较特殊，假设小杨选择的宝箱中最大价值为 $x$，最小价值为 $y$，小杨需要保证 $x-y\leq k$，否则小杨的背包会损坏。
小杨想知道背包不损坏的情况下，自己能够带走宝箱的总价值最大是多少。
输入格式
第一行包含两个正整数 $n,k$，含义如题面所示。
第二行包含 $n$ 个正整数 $a_1,a_2,\dots,a_n$，代表宝箱的价值。
输出格式
输出一个整数，代表带走宝箱的最大总价值。
输入输出样例 #1
输入 #1
1
2
5 1
1 2 3 1 2
输出 #1
1
7
说明/提示
【样例解释】:
在背包不损坏的情况下，小杨可以拿走两个价值为 $2$ 的宝箱和一个价值为 $3$ 的宝箱。
【数据范围】:
对于全部数据，保证有 $1\leq n\leq 1000$，$0\leq k\leq 1000$，$1\leq a_i\leq 1000$。
题目分析
本题可以采用两种思路来解决:
方法一：前缀和方法
- 首先对所有宝箱价值进行排序，这样可以保证最大值最小值的差值是连续的
- 预处理前缀和数组，用于快速计算任意区间的宝箱价值之和
- 枚举所有可能的价值范围（双重循环）：
- 外层循环 i 表示当前范围的最小值
- 内层循环 j 表示当前范围的最大值
- 如果
val[j] - val[i] ≤ k，则使用前缀和计算该范围内的总价值 - 由于数组已排序，一旦发现不满足条件可直接break内层循环
- 维护并更新最大总价值
时间复杂度：
- 排序需要 $O(n\log n)$
- 计算前缀和需要 $O(n)$
- 双重循环枚举价值范围需要 $O(n^2)$
- 总体时间复杂度为 $O(n^2)$
空间复杂度：
- 需要额外的前缀和数组，空间复杂度为 $O(n)$
方法二：滑动窗口（双指针）方法
- 同样先对宝箱价值排序
- 使用左右两个指针维护一个滑动窗口：
- 右指针不断向右扩展窗口，将新的宝箱加入总和
- 当窗口内最大值与最小值的差超过k时，左指针右移缩小窗口
- 由于数组有序，右指针位置即为当前窗口最大值，左指针位置即为最小值
- 在窗口滑动过程中维护最大总价值
时间复杂度：
- 排序需要 $O(n\log n)$
- 滑动窗口只需要遍历一次数组，$O(n)$
- 总体时间复杂度为 $O(n\log n)$
空间复杂度：
- 只需要存储原始数组，空间复杂度为 $O(n)$
对于本题的数据范围($n\leq1000$)，两种方法都可以通过，但滑动窗口方法在处理更大规模数据时具有明显优势。
示例代码
方法一： 前缀和
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
36
37
38
39
40
41
42
43
44
#include <algorithm>
#include <iostream>
// 存储宝箱价值的数组
int val_arys[1005];
// 存储前缀和的数组
int pre_sum[1005];
int main() {
// 读入宝箱数量n和最大价值差k
int n, k;
std::cin >> n >> k;
// 读入每个宝箱的价值
for (int i = 0; i < n; i++) {
std::cin >> val_arys[i];
}
// 对宝箱价值进行排序，便于后续处理
std::sort(val_arys, val_arys + n);
// 计算第一个前缀和
pre_sum[0] = val_arys[0];
// 计算所有前缀和
for (int i = 1; i < n; i++) {
pre_sum[i] = pre_sum[i - 1] + val_arys[i];
}
// 记录最大总价值
int max_sum = 0;
// 枚举所有可能的价值范围
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
// 如果当前价值范围满足条件(最大值减最小值不超过k)
if (val_arys[j] - val_arys[i] <= k) {
// 使用前缀和计算当前范围内的总价值并更新最大值
max_sum =
std::max(max_sum, pre_sum[j] - pre_sum[i] + val_arys[i]);
} else {
// 由于数组已排序，如果当前j位置与i位置的差值超过k
// 后续的差值一定更大，可以直接跳出内层循环
break;
}
}
}
// 输出结果
std::cout << max_sum;
return 0;
}
方法二： 滑动窗口(双指针)
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
36
37
38
39
40
41
42
43
44
45
#include <algorithm>
#include <iostream>
// 存储宝箱价值的数组
int val_arys[1005];
int main() {
// 读入宝箱数量n和最大价值差k
int n, k;
std::cin >> n >> k;
// 读入每个宝箱的价值
for (int i = 0; i < n; i++) {
std::cin >> val_arys[i];
}
// 对宝箱价值进行排序，便于使用滑动窗口
std::sort(val_arys, val_arys + n);
// 记录最大总价值
int max_sum = 0;
// 滑动窗口左边界
int left = 0;
// 当前窗口内的价值总和
int cur_sum = 0;
// 滑动窗口右边界向右移动
for (int right = 0; right < n; right++) {
// 将右边界的宝箱加入当前总和
cur_sum += val_arys[right];
// 当窗口内最大值与最小值的差超过k时
// 不断移动左边界直到满足条件
// 由于数组已排序，right位置的值一定是当前窗口最大值
// left位置的值一定是当前窗口最小值
while(val_arys[right] - val_arys[left] > k) {
// 移除窗口最左边的值，需要从当前和中减去
cur_sum -= val_arys[left];
// 左边界右移一位，缩小窗口范围
// 由于数组有序，新的left位置值一定大于之前的值
// 这样可以逐步减小最大值和最小值的差，直到满足条件
left++;
}
// 更新最大总价值
max_sum = std::max(max_sum, cur_sum);
}
// 输出结果
std::cout << max_sum;
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)，考试认证学员交流，互帮互助
