宝箱 题解

题目分析

我们有 $n$ 个宝箱，每个宝箱有一个价值 $a_i$。我们需要从中选择一些宝箱带走，选择的宝箱中最大值 $x$ 与最小值 $y$ 的差不能超过 $k$，即 $x - y \leq k$。目标是在满足条件的前提下最大化所选宝箱的总价值。

注意：所有宝箱的价值都是正整数，并且选择时只关心价值的范围，与宝箱的原始顺序无关。

解题思路

由于只关心价值的范围，我们可以先把所有宝箱按价值从小到大排序。排序后，满足条件的选择必然是序列中连续的一段。为什么？

• 假设我们选中了排序后不连续的一些宝箱，中间有未选中的宝箱。因为所有价值都非负，我们把中间未选中的宝箱也带上，总价值一定不会变小，而且最大值和最小值不变，条件依然满足。
• 因此，最优解一定对应排序后价值连续的一个区间。

问题转化为：在排好序的数组中，找一个区间，使得区间的最大值与最小值之差 $\leq k$，并且区间内所有元素的和最大。

算法说明

基础算法（枚举 + 求和）

1. 读入 $n, k$ 和价值数组 $a$。
2. 对 $a$ 进行升序排序。
3. 初始化答案 $ans = 0$。
4. 枚举区间的右端点 $i$（即当前区间的最大值）：
   • 从左端点 $j = i$ 开始向左移动，同时累加 $a_j$ 到当前和 $sum$ 中。
   • 当 $a[i]-a[j]>k$ 时停止，因为再往左价值差会超过 $k$。
   • 更新 $ans = \max(ans, sum)$。
5. 输出 $ans$。

这种做法简单直观，对应题目的参考代码。由于 $n \leq 1000$，最坏情况下内层循环执行约 $n^2/2$ 次，可以轻松通过。

优化思路（双指针/滑动窗口）

如果数据范围更大，可以进一步优化：

• 使用双指针（滑动窗口）：左指针 $l$ 和右指针 $r$ 都从 $1$ 开始，维护窗口内元素的和 $sum$。
• 当 $a[r] - a[l] \leq k$ 时，不断右移 $r$，累加 $a[r]$ 并更新答案。
• 当差值超过 $k$ 时，右移 $l$，从 $sum$ 中减去 $a[l]$。
• 时间复杂度降为 $O(n \log n)$（排序）+ $O(n)$（双指针），总体 $O(n \log n)$。

对于本题 $n=1000$ 的数据范围，简单的双重循环即可，代码也更容易编写和理解。

时间复杂度分析

• 排序：$O(n \log n)$。
• 双重循环枚举 + 求和：最坏 $O(n^2)$。
• 总复杂度：$O(n^2)$，对于 $n=1000$ 是完全可以接受的，$10^6$ 级别的运算在 1 秒内绰绰有余。
• 空间复杂度：$O(n)$，用于存储数组。

参考代码及解释

以下为题目提供的 C++ 参考代码，并附有详细注释：

cpp
复制
1#include<bits/stdc++.h>
2using namespace std;
3const int N = 1010;
4int a[N];
5int n, k;
6
7int main(){
8    // 输入
9    cin >> n >> k;
10    for(int i = 1; i <= n; i++){
11        cin >> a[i];
12    }
13
14    // 按价值升序排序
15    sort(a + 1, a + n + 1);
16
17    int ans = 0;
18    // 枚举区间的右端点（最大值）
19    for(int i = 1; i <= n; i++){
20        int sum = 0;
21        // 从 i 向左扩展左端点，直到差值超过 k
22        for(int j = i; j >= 1; j--){
23            if(a[i] - a[j] <= k){
24                sum += a[j];   // 累加仍在范围内的宝箱价值
25            } else {
26                break;         // 超出范围，停止左扩
27            }
28        }
29        ans = max(ans, sum);   // 更新最大总价值
30    }
31
32    cout << ans << "\n";
33    return 0;
34}

代码要点解释：

• sort(a + 1, a + n + 1)：排序后可以保证价值相近的宝箱相邻，符合“连续区间”的贪心基础。
• 外层循环 i 代表当前选中的最大值所在的位置。
• 内层循环 j 从 i 开始向左扫描，只要满足 a[i]-a[j] <= k 就将 a[j] 加入 sum，一旦不满足就跳出。
• 每次更新 ans 为当前最大值。
• 最后输出答案。

如果你想进一步提高效率，可以预习前缀和和双指针优化。但作为解题，上述方法已经足够通过所有测试数据。