【枚举+贪心】CF1409 E

叁歲伎倆 2024-03-01 07:49 128阅读 0赞

[Problem - E - Codeforces][]

题意：

![692b4193a8eb4cbf9d366556390ec556.png][]

![316811956368434ca49ba349a5e9d9aa.png][]

思路：

首先贪心的结论很明显，选两个贡献最大的区间

还有一个结论，这两个区间没有交点

然后就能直接做了，枚举一个区间，然后找这个区间后缀的最大贡献的区间即可，所以需要维护一个后缀贡献的最大值

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using namespace std;
    
    constexpr int N = 2e5 + 10;
    constexpr int mod = 998244353;
    
    int n, k;
    int x[N], y[N];
    int dp[N];
    int mx[N];
    
    void solve() {
        std::cin >> n >> k;
        for (int i = 0; i <= n + 1; i ++) {
            mx[i] = 0;
            dp[i] = 0;
        }
        for (int i = 1; i <= n; i ++) std::cin >> x[i];
        for (int i = 1; i <= n; i ++) std::cin >> y[i];
        
        std::sort(x + 1, x + 1 + n);
    
        for (int i = 1; i <= n; i ++) {
            int r = std::upper_bound(x + 1, x + 1 + n, x[i] + k) - x - 1;
            dp[i] = r - i + 1;
        }
    
        for (int i = n; i >= 1; i --) {
            mx[i] = std::max(mx[i + 1], dp[i]);
        }
    
        int ans = 0;
        for (int i = 1; i <= n; i ++) {
            ans = std::max(ans, dp[i] +  mx[i + dp[i]]);
        }
    
        std::cout << ans << "\n";
    }
    signed main() {
        std::ios::sync_with_stdio(false);
        std::cin.tie(nullptr);
    
        int t = 1;
        std::cin >> t;
        while(t --) {
            solve();
        }
        return 0;
    }

[Problem - E - Codeforces]: https://codeforces.com/contest/1409/problem/E
[692b4193a8eb4cbf9d366556390ec556.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/01/2a37c05ca4b143d188c440589cad5e58.png
[316811956368434ca49ba349a5e9d9aa.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/01/6246c6316eeb4a1a90a2de98709293d1.png