【枚举+贪心】CF1409 E

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

Problem - E - Codeforces

题意：

692b4193a8eb4cbf9d366556390ec556.png

316811956368434ca49ba349a5e9d9aa.png

思路：

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

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

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

Code：

  1. #include <bits/stdc++.h>
  3. #define int long long
  5. using namespace std;
  7. constexpr int N = 2e5 + 10;
  8. constexpr int mod = 998244353;
  10. int n, k;
  11. int x[N], y[N];
  12. int dp[N];
  13. int mx[N];
  15. void solve() {
  16.     std::cin >> n >> k;
  17.     for (int i = 0; i <= n + 1; i ++) {
  18.         mx[i] = 0;
  19.         dp[i] = 0;
  20.     }
  21.     for (int i = 1; i <= n; i ++) std::cin >> x[i];
  22.     for (int i = 1; i <= n; i ++) std::cin >> y[i];
  24.     std::sort(x + 1, x + 1 + n);
  26.     for (int i = 1; i <= n; i ++) {
  27.         int r = std::upper_bound(x + 1, x + 1 + n, x[i] + k) - x - 1;
  28.         dp[i] = r - i + 1;
  29.     }
  31.     for (int i = n; i >= 1; i --) {
  32.         mx[i] = std::max(mx[i + 1], dp[i]);
  33.     }
  35.     int ans = 0;
  36.     for (int i = 1; i <= n; i ++) {
  37.         ans = std::max(ans, dp[i] +  mx[i + dp[i]]);
  38.     }
  40.     std::cout << ans << "\n";
  41. }
  42. signed main() {
  43.     std::ios::sync_with_stdio(false);
  44.     std::cin.tie(nullptr);
  46.     int t = 1;
  47.     std::cin >> t;
  48.     while(t --) {
  49.         solve();
  50.     }
  51.     return 0;
  52. }

发表评论

表情：
评论列表 （有 0 条评论，164人围观）

还没有评论，来说两句吧...

相关阅读