GESP 题解库 / 4 级题解 / [GESP202406 四级] 宝箱 · 第 12 / 25 题
GESP202406 四级 · B4006 · 简单

宝箱

选若干宝箱,要求所选价值最大值与最小值之差 ≤ k,求能带走的最大总价值。

📊
n ≤ 1000
宝箱数
🔢
aᵢ, k ≤ 1000
数值范围
⚡
O(n²)
时间复杂度
🎯
排序 + 枚举区间
核心算法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

有 n 个宝箱,第 i 个价值 aᵢ。小杨可以选一些带走,但背包要求:所选宝箱中最大价值 x 与最小价值 y 满足 x − y ≤ k,否则背包会损坏。

求背包不损坏的情况下,能带走宝箱的最大总价值。

💡
人话翻译:所选宝箱的"价值跨度"不能超过 k。关键洞察:把价值排序后,如果某个集合满足"跨度 ≤ k",那么把它补齐成一段连续区间(在排序数组上)只会让总和更大、跨度不变。所以问题变成:排序后,枚举所有跨度 ≤ k 的连续区间,取最大和。

🔍 关键词提取

排序连续区间枚举前缀和极差约束

已知条件

项目说明
输入第一行 n、k;第二行 n 个正整数
输出最大总价值
数据范围1 ≤ n ≤ 1000
数值范围0 ≤ k ≤ 1000,1 ≤ aᵢ ≤ 1000
约束所选集合的 max − min ≤ k

需要解决的问题

02
思维导图
整理解题思路的全貌
💰 排序 + 区间枚举
🧠 核心转化
所选集合跨度 ≤ k
补齐中间的数不会让跨度变大
但会让总和变大
⇒ 最优解必是连续区间
📥 排序
升序排序
跨度 = a[r] − a[l]
重复值可以全选
n ≤ 1000 可 O(n²)
🔍 枚举区间
l 从 0 到 n−1
r 从 l 往后扩
直到 a[r] − a[l] > k 停止
用前缀和求区间和
⚠️ 易错点
忘记"可以只选一部分"
跨度写成 < k 而非 ≤ k
未排序导致枚举无效
前缀和下标偏移
03
样例手算推导
样例 5 个宝箱的最优区间

🧮 样例:n = 5,k = 1,价值 1 2 3 1 2,答案 7

先排序,再枚举所有跨度 ≤ 1 的区间。

步骤内容
原数组1, 2, 3, 1, 2
排序后1, 1, 2, 2, 3
下标0, 1, 2, 3, 4

枚举所有跨度 ≤ 1 的区间

区间元素跨度是否 ≤ 1区间和
[0,0]10✅1
[0,1]1, 10✅2
[0,2]1, 1, 22 − 1 = 1✅4
[0,3]1, 1, 2, 22 − 1 = 1✅6
[0,4]1, 1, 2, 2, 33 − 1 = 2❌—
[1,2]1, 21✅3
[1,3]1, 2, 21✅5
[2,3]2, 20✅4
[2,4]2, 2, 33 − 2 = 1✅7
[3,4]2, 31✅5
[4,4]30✅3
1
最大区间和是 7

区间 [2,4] = {2, 2, 3},跨度 3 − 2 = 1 ≤ 1

总和 = 2 + 2 + 3 = 7

另一个候选 [0,3] = {1, 1, 2, 2} 总和 6,更小

✅ 答案 7

2
与题面解释对照

题面说"拿走两个价值为 2 的宝箱和一个价值为 3 的宝箱"

正是 {2, 2, 3},总和 7 ✓

注意 aᵢ = 1 的两个宝箱没被选中——因为一旦选它们,跨度就变成 3 − 1 = 2 > k

✅ 完全吻合

🔑
注意"1 和 3 不能同时选":本文样例中 k = 1,所以跨度最多为 1。价值 1 和 3 跨度为 2,超出限制,因此只能在"低位区"(1 和 2)或"高位区"(2 和 3)中选一段。最终 {2, 2, 3} 的和更大。

🧮 边界情形

情形数据分析答案
k = 0a = [5, 5, 3]跨度必须为 0 → 只能选全部相同的值10(两个 5)
只有一个宝箱a = [7]必选7
全部相同a = [4, 4, 4]跨度 0,全选12
k 足够大a = [1, 100], k = 99跨度 99 ≤ 99,可以全选101
⚠️
注意 k 可能为 0:此时只能选完全相同的价值,答案就是"出现次数最多的那个值的出现次数 × 该值"。写代码时不要假设 k > 0。
04
解法对比
排序 + 前缀和 O(n²) vs 双指针 O(n)

⚔️ 解法对比

🟢 排序 + 枚举区间(推荐) 推荐

排序后双层循环枚举左右端点,用前缀和求和

  • 时间 O(n²)
  • n = 1000 时约 5 × 10⁵ 次
  • 代码 12 行
  • 直观好写
💡
实现要点:固定左端点 l,让 r 向右扩展,一旦 a[r] - a[l] > k 就停止(再往右只会更大)。

🟠 双指针 O(n)

随着 l 右移,r 也单调右移,用滑动窗口维护区间和

  • 时间 O(n)
  • 代码稍复杂
  • 需要处理窗口和的增减
  • 本题属于锦上添花
⚠️
为什么单调:l 增大时 a[l] 变大,窗口右端 r 的最远位置只会更远或不变,所以 r 可以继承上一轮的位置不回头,整体是 O(n)。

📈 性能对比

方案本题运算量n = 10⁵ 时
排序 + 枚举约 5 × 10⁵约 5 × 10⁹(超时)
双指针约 10³约 1.7 × 10⁶(可行)
05
算法流程图
排序 → 枚举左端点 → 扩展右端点
开始读入 n、k 和数组 a;排序 a预处理前缀和 pre[];ans = 0l 从 0 到 n−1r 从 l 向右扩展,直到 a[r] − a[l] > k区间和 = pre[r] − pre[l];ans = max(ans, 区间和)所有左端点都试过了吗?输出 ans结束l 加 1 继续
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

💰 宝箱选择计算器

第一行输入价值和 k(用 | 分隔),程序会排序并枚举所有跨度 ≤ k 的区间。

结果会显示在这里

点按钮开始 →

07
代码精讲
逐段拆解,彻底搞懂

💻 完整 C++ 代码

#include <bits/stdc++.h>
using namespace std;

int a[1005];
long long pre[1005];

int main() {
    int n, k;
    scanf("%d %d", &n, &k);
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);

    sort(a, a + n);                     // 排序后,最优解对应一段连续区间

    // 前缀和:pre[i] = a[0] + ... + a[i-1]
    pre[0] = 0;
    for (int i = 0; i < n; i++) pre[i + 1] = pre[i] + a[i];

    long long ans = 0;
    for (int l = 0; l < n; l++) {
        for (int r = l; r < n; r++) {
            if (a[r] - a[l] > k) break;          // 跨度超标,再往右只会更大
            long long sum = pre[r + 1] - pre[l]; // 区间 [l, r] 的和
            if (sum > ans) ans = sum;
        }
    }

    printf("%lld\n", ans);
    return 0;
}
🔑
为什么内层循环能 break?因为数组已经升序,随着 r 增大 a[r] 只增不减,所以 a[r] - a[l] 也会单调增大。一旦超标,后面全部超标,直接 break 就能省掉大量无用检查。

📖 关键几行怎么看

代码作用为什么这样写
sort(a, a + n)排序让"跨度"对应连续区间的端点差
pre[i+1] = pre[i] + a[i]前缀和使区间和查询变成一次减法
if (a[r] - a[l] > k) break;跨度检查超标就停,因为后面更大
pre[r+1] - pre[l]区间和注意上界是 r+1 而不是 r
⚠️
三个坑:① 不排序就枚举(那样"跨度 ≤ k 的最优集合"无法用连续区间表示);② 跨度判断写成 < k(题目是 ≤ k);③ 前缀和下标写错:区间 [l, r] 的和是 pre[r+1] - pre[l]。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

写完程序后,用这些数据自查一遍:

输入答案考察点
5 1
1 2 3 1 2
7题面样例
1 0
7
7单个宝箱,必选
3 0
5 5 3
10k = 0 只能选相同的值,两个 5 得 10
3 100
1 2 3
6k 很大,全部可以选
4 2
10 20 30 40
40相邻两数相差 10 > k = 2,任何两个都不能同选,最大为 40
3 5
1 4 6
116 − 1 = 5 ≤ 5,三个都选得 11
✅
自查清单:① 排序了吗?② 跨度用的是 ≤ 吗?③ 前缀和下标对吗?

🚨 易错点清单

⚠️
不排序就枚举:必须排序,否则"最优集合是连续区间"这个性质不成立。
⚠️
跨度写成严格小于:题目要求 max − min ≤ k,包含等于的情况。
⚠️
前缀和下标错位:区间 [l, r] 的和是 pre[r+1] − pre[l]。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O(n²)
空间复杂度
O(n)
n 最大
1000
最坏运算
约 5 × 10⁵

时间怎么算的?

空间都用在哪?

需要存数组与前缀和数组。

✅ 约 50 万次操作,瞬间完成。如果 n 达到 10⁵,就要改用双指针滑动窗口。

10
知识拓展
学一道题,会一类题

🔗 常用技巧小抄

// 核心结论:排序后,满足"极差 ≤ k"的最优子集一定对应一段连续区间
// 证明直觉:若最优集合的最小值在位置 l、最大值在位置 r,
//          则把 [l, r] 中所有元素都选上,极差不变(仍是 a[r]-a[l]),
//          但总和变大 -> 所以连续区间必然不劣于原集合。

// 前缀和求区间和
long long rangeSum(int l, int r) { return pre[r+1] - pre[l]; }

// 双指针 O(n) 版本(n 很大时用)
long long best = 0, cur = 0;
int r = 0;
for (int l = 0; l < n; l++) {
    while (r < n && a[r] - a[l] <= k) { cur += a[r]; r++; }
    best = max(best, cur);
    cur -= a[l];              // 左端点右移,去掉 a[l]
}

// 类似的"极差约束"题目都可以用这个套路

🌟 举一反三

把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。

能力点本题怎么用还能迁移到
排序 + 连续区间极差约束 → 排序后枚举区间选数最大化、预算分配、区间最值
前缀和求区间和O(1) 查询所有需要反复求区间和的题
单调性 break差值单调 → 可提前终止优化枚举的常用技巧
🌟
思考题:如果题目改成"所选个数最多"(而不是总价值最大),策略会变吗?(提示:策略不变——同样是排序后枚举跨度 ≤ k 的最长连续区间,只是把"求最大和"换成"求最大长度"。这也说明"排序 + 连续区间"是这类极差约束问题的通用框架。)