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

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

2个月前 (06-25)

2024年GESP四级宝箱题(洛谷P4006)题解:滑动窗口算法优化最长子序列和 GESP四级 洛谷 滑动窗口算法 双端队列 动态规划优化 第1张

一、题目解读

本题为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;  
}

五、总结

本解法通过排序+滑动窗口实现线性时间复杂度,关键在于利用有序队列维护窗口边界,避免了暴力枚举的指数级复杂度。适用于求解“带范围约束的最优子序列”问题,对同类题目(如区间最值差限制下的优化问题)具有借鉴意义。同时,双端队列的灵活操作为窗口动态调整提供了高效工具。

原创内容 转载请注明出处

分享给朋友:

相关文章

IOI 1994 洛谷1216:如何用动态规划高效解决数字三角形问题?附完整代码解析

IOI 1994 洛谷1216:如何用动态规划高效解决数字三角形问题?附完整代码解析

题目重解给定一个由数字组成的三角形结构,从顶部出发,每次可以移动到下方相邻的数字,最终到达底部。我们的目标是找到一条路径,使得路径上经过的数字总和最大。这个问题在实际中有许多应用场景,如最优路径规划、...

牛客14778题解析:滑动窗口算法破解字符替换问题的最优解

牛客14778题解析:滑动窗口算法破解字符替换问题的最优解

一、题目解读牛客14778题要求给定字符串s、替换次数上限m及目标字符,求解在s中通过最多m次替换操作,得到的最长连续子串长度。例如,当s="abcbab",m=2,target=...

【洛谷1184题解析】用C++高效解决地点匹配问题(附代码与解题思路)

【洛谷1184题解析】用C++高效解决地点匹配问题(附代码与解题思路)

一、题目解读洛谷1184题要求处理一组地点列表与行程记录,统计其中匹配的天数。题目难点在于高效处理带有空格的字符串输入,以及快速判断每日行程是否在高手可去地点集合中。需要兼顾输入格式解析与算法效率。二...

2023年GESP四级田忌赛马算法解析(洛谷B3928)— C++双指针策略与代码详解

2023年GESP四级田忌赛马算法解析(洛谷B3928)— C++双指针策略与代码详解

一、题目解读“田忌赛马”源自中国古代典故,田忌通过策略性安排马匹对阵顺序,以弱马对阵强马、强马对阵弱马的方式,实现整体胜利。在算法竞赛中,该问题通常转化为:给定两方马匹的战斗力数组,如何通过对阵策略最...

2023年GESP四级小杨的字典(洛谷B3927)解题报告:基于哈希表的字符串替换优化

2023年GESP四级小杨的字典(洛谷B3927)解题报告:基于哈希表的字符串替换优化

一、题目解读题目要求实现一个“字典替换”功能:给定一个字典(键值对映射)和一段文本,将文本中出现的字典中的单词替换为其对应的值,未匹配的单词用“UNK”代替。需处理标点符号分隔单词,并确保输入异常情况...

发表评论

访客

看不清,换一张

◎欢迎参与讨论,请在这里发表您的看法和观点。