G4010 [GESP202406 四级] 宝箱 题解

知识点：排序、双指针、滑动窗口、前缀累计。

解题思路

把数值升序排列，双指针维护最大值减最小值不超过k的窗口，并维护窗口总和，取最大总和。

为什么正确

固定右端点后，将左端移到首个合法位置会保留所有可选正数，因此得到该右端的最大合法收益。

易错点

边界差等于k仍合法；总收益用long long，移动左指针时同步减去元素。

复杂度

时间O(n log n)，空间O(n)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,k;
    cin>>n>>k;
    vector<int>a(n);
    for(int &x:a)cin>>x;
    sort(a.begin(),a.end());
    long long ans=0,sum=0;
    int l=0;
    for(int h=0;h<n;h++) {
        sum+=a[h];
        while(a[h]-a[l]>k)sum-=a[l++];
        ans=max(ans,sum);
    }
    cout<<ans;
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用10个自行生成的测试点。