2024年GESP四级宝箱题（洛谷P4006）题解：滑动窗口算法优化...
https://www.xinaozhilu.cn/zb_users/upload/2025/06/202506231750676914232042.jpg一、题目解读本题为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; // 读取宝箱价值
}
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; // 加入当前元素至和
q.push_back(a); // 元素入队
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）题解：滑动窗口算法优化最长子序列和
页:
[1]