当前位置：首页 > GESP > 2024年GESP四级宝箱题（洛谷P4006）题解：滑动窗口算法优化最长子序列和

2024年GESP四级宝箱题（洛谷P4006）题解：滑动窗口算法优化最长子序列和

1个月前 (06-25)

一、题目解读

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

二、解题思路

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

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

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

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

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

三、解题步骤

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

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

3. 滑动窗口循环：

○ 右边界右移：加入a[i]至队列，更新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;  
}