2024GESP四级宝箱问题（洛谷B4006）：滑动窗口算法的精妙应用

一、问题解析

小杨发现了n个价值各异的宝箱，需要选择其中若干个带走。但背包有特殊限制：选择的宝箱中最大价值与最小价值的差不能超过k。我们的目标是找出满足条件下能带走的最大总价值。

二、算法解析

1. 排序预处理： 首先将宝箱按价值排序，这样我们可以方便地使用滑动窗口技术来控制最大最小值的差值。

2. 滑动窗口技术：

• 使用双端队列维护当前窗口内的宝箱

• 窗口条件：最大值(队尾) - 最小值(队首) ≤ k

• 当条件不满足时，从队首移除最小的宝箱直到条件满足

3. 动态维护总和：

• 实时计算当前窗口内宝箱的总价值

• 维护一个全局最大值记录最优解

三、完整代码

#include <bits/stdC++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, k;
    cin >> n >> k;
    
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    
    sort(a.begin(), a.end()); // 将宝箱按价值排序
    
    ll max_sum = 0, current_sum = 0;
    deque<int> q; // 维护滑动窗口的双端队列
    
    for (int i = 0; i < n; ++i) {
        current_sum += a[i]; // 加入当前宝箱价值
        q.push_back(a[i]);   // 加入队列
        
        // 维护窗口条件：最大值-最小值≤k
        while (!q.empty() && q.back() - q.front() > k) {
            current_sum -= q.front(); // 移除超出范围的宝箱
            q.pop_front();
        }
        
        max_sum = max(max_sum, current_sum); // 更新最大值
    }
    
    cout << max_sum << "\n";
    return 0;
}

四、新手学习建议

1. 首先理解题目要求：我们需要选择一组宝箱，使得它们的最大值和最小值之差不超过k，同时总和最大。

2. 排序是关键步骤，因为它让我们能够轻松控制最大值和最小值的差值。

3. 滑动窗口技术是解决这类区间问题的常用方法，需要熟练掌握。

4. 注意处理边界情况，如所有宝箱价值相同或k=0的情况。

扩展思考

1. 如果宝箱价值可能有负数，算法需要如何调整？

2. 如果要求必须选择至少m个宝箱，算法又该如何修改？

3. 尝试用其他数据结构(如堆)来实现相同的功能，比较效率差异。

参考：2024年GESP四级宝箱题解