组队题解(含追逐思想)
解题思路:
- 先将所有数从大到小排,后定义一个区间的左右端点l,r,先固定左端点,右端点不断向前移动,直到两端点的差值大于K,再向前移动一格左端点,注意!!右端点没有必要重新开始(后退),因为再往后移差值肯定小于K,但区间不够大。
- 追逐思想(毛虫思想):左右两端点,右端点没有必要后退。
- (1、有左右端点 2、区间大小会变,移来移去)
AC代码如下:
#include<bits/stdc++.h>
using namespace std;
int main(){
int T;
cin>>T;
while(T--){
int n,k,i,a[200020],l,r,long=0;
cin>>n>>k;
for(i=0;i<n;i++) cin>>a[i];
sort(a,a+n);
for(l=0,r=0;l<n;l++){
while(r<n&&a[r]-a[l]<=k) r++;//r必须在这里约束否则r会不停增加
long=max(long,r-l);
}
cout<<long<<endl;
}
return 0;
}