欢乐赛 #66 T6 题解

使用双指针解决。

先将 $a_1,a_2\cdots,a_n$ 从小到大排序。

初始时，左指针 $l$ 与当右指针 $r$ 的值均为 $1$。

当 $r\le n$ 时：

• 不断右移 $r$ 直到此区间最大最小差超过 $y$；
• 计算此区间最大最小差超过 $y$ 之前的长度，与最大值比较；
• 不断右移 $l$ 直到此区间最大最小差不超过 $y$；
• 计算此区间长度，与最大值比较（因为可以证明，此区间长度一定不超过之前的区间长度，所以可以省略）。

#include <bits/stdc++.h>
using namespace std;
int n,y,ans;
int a[1000005];
int main(){
	cin>>n>>y;
    for (int i=1;i<=n;i++){
        cin>>a[i];
    }
    sort(a+1,a+n+1);
    int l=1,r=1;
    while (r<=n){
        while (a[r]-a[l]<=y&&r<=n){//边界条件
            r++;
        }
        ans=max(r-l,ans);//此时区间长度为符合题意的区间长度 +1，所以不需要 r-l+1
        while (a[r]-a[l]>y){
            l++;
        }//补充说明一下，之前的区间长度只增加了 1，而此区间长度至少增加 1，所以不需要比较
    }
    cout<<ans;
	return 0;
}