2024年GESP四级宝箱题（洛谷P4006）题解：滑动窗口算法优化...

19339201706 · 发表于 6 天前

一、题目解读

本题为2024年GESP四级中的“宝箱”问题（对应洛谷P4006），要求在一个由n个宝箱组成的序列中，找出一个连续子序列，使得该子序列中宝箱价值之和最大，且子序列中最大值与最小值的差不超过k。题目核心在于平衡子序列长度与数值范围约束，属于典型的动态规划与窗口优化类问题。

二、解题思路

采用滑动窗口 + 双端队列的策略：

1. 对宝箱价值数组进行升序排序，确保窗口内元素有序；

2. 维护一个动态窗口，通过双端队列存储元素，保证队列头部为当前窗口最小值，尾部为最大值；

3. 通过移动窗口右边界并动态调整左边界（弹出超出范围的最小值），实时计算满足条件的最长子序列和。

核心思想：利用有序性减少遍历复杂度，队列维护窗口边界，实现O(n)高效求解。

三、解题步骤

1. 输入与预处理：读取n（宝箱数量）和k（差值阈值），存入数组a并排序；

2. 初始化窗口：双端队列q记录元素，当前和current_sum初始化为0；

3. 滑动窗口循环：

○ 右边界右移：加入a至队列，更新current_sum；

○ 左边界调整：若队列尾-队列头 > k，弹出队头元素并减少当前和；

○ 更新答案：max_sum记录当前窗口的最大和；

4. 输出结果：最终max_sum即为目标值。

四、代码与注释
#include <bits/stdC++.h>

using namespace std;

using ll = long long;

int main() {

ios::sync_with_stdio(false); // 关闭同步，加快IO

cin.tie(nullptr);



int n, k;

cin >> n >> k;             // 输入宝箱数量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]);    // 元素入队

      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;

}
复制代码

五、总结
本解法通过排序+滑动窗口实现线性时间复杂度，关键在于利用有序队列维护窗口边界，避免了暴力枚举的指数级复杂度。适用于求解“带范围约束的最优子序列”问题，对同类题目（如区间最值差限制下的优化问题）具有借鉴意义。同时，双端队列的灵活操作为窗口动态调整提供了高效工具。
转发：2024年GESP四级宝箱题（洛谷P4006）题解：滑动窗口算法优化最长子序列和