前缀和做法

使用一个 $dpdp$ 数组记录前缀和，$d{p}_{i}dp\_i$ 表示在 $[0,i][0,i]$ 中有多少个点。

枚举起点 $ii$ 即可得到线段终点 $i+k-1i+k-1$ , 使用 $d{p}_{i+k-1}-d{p}_{i-1}dp\_\{i+k-1\}-dp\_\{i-1\}$ 即可得到这段中的点的数量

本题做法很多，双指针也可做，随便乱搞就行，复杂度都一样

#include<bits/stdc++.h>
using namespace std;

int dp[1100000] , n , k;

int main() {
    scanf("%d%d",&n,&k);
    int max_ = 0 , min_ = 0x3f3f3f;
    for (int i = 1 ; i <= n ; i ++) {
        int tmp;
        scanf("%d",&tmp);
        max_ = max(max_,tmp);
        min_ = min(min_,tmp);
        dp[tmp] = 1;
    }
    for (int i = min_ ; i <= max_ ; i ++) {
        dp[i] = dp[i]+dp[i-1];
    }
    int res = 0;
    if (k >= (max_-min_+1)) {
        printf("%d\n",n);
        return 0;
    }
    for (int i = min_ ; i+k-1 <= max_ ; i ++) {
        res = max(res,dp[i+k-1]-dp[i-1]);
    }
    printf("%d\n",res);
}