Atcoder-abc326_c 题解

发表于2023-11-05更新于2023-11-05

题目传送门

一道二分题……

首先非常显然，你选择的这个区间左端点在 aia_i 上肯定更优，因此我们可以枚举左端点 ll。然后剩下的就是使用二分求出有多少个 aia_i 满足 l≤ai<l+ml\le a_i< l+m，具体可以使用 std :: upper_bound 实现。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <bits/stdc++.h>

const long long IMX = 1ll << 30;
const long long LMX = 1ll << 60;

typedef long long ll;
typedef __int128 i128;
typedef long double ld;
typedef __float128 f128;

namespace xvl_ { 
    #define SP(n, x) std :: setprecision(n) << std :: fixed << x
    #define REP(i, l, r) for (auto i = (l); i <= (r); i++)
    #define PER(i, r, l) for (auto i = (r); i >= (l); i--)
    #define DEBUG(x) std :: cerr << #x << " = " << x << '\n'
    template <typename T> T Max(T a, T b) { return a > b ? a : b; } template <typename T, typename... Args> T Max(T a, Args... args) { return a > Max(args...) ? a : Max(args...); }
    template <typename T> T Min(T a, T b) { return a < b ? a : b; } template <typename T, typename... Args> T Min(T a, Args... args) { return a < Min(args...) ? a : Min(args...); }
}
using namespace std;
using namespace xvl_;
ll n, m, ans;
int a[300005];
int main() {
    // freopen("InName.in", "r", stdin);
    // freopen("OutName.out", "w", stdout);
    ios :: sync_with_stdio(0);
    cin.tie(nullptr);
    cin >> n >> m;
    REP(i, 1, n) cin >> a[i];
    sort(a + 1, a + 1 + n);
    REP(i, 1, n) {
        ll loc = upper_bound(a + 1, a + 1 + n, a[i] + m - 1) - a - 1;
        ans = Max(ans, loc - i + 1);
    }
    cout << ans;
    return 0;
}