组队题解(含追逐思想)

alt

解题思路:

  • 先将所有数从大到小排,后定义一个区间的左右端点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;
}