关于尺取
查看原帖
关于尺取
250699
mot1ve楼主2020/10/5 21:29

我这题用尺取做的,我只会放一个架子的情况,但这个题是两个架子,看题解用尺取做的没大看明白,能提供一下思路吗?

//先把一个架子的情况写出来,尺取就ok,推进左端点和右端点 
#include<bits/stdc++.h>
using namespace std;
int n,k,l,r,ans;
int a[100010];
int main() 
{
	cin>>n>>k;
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
	}
	sort(a+1,a+1+n);
	l=1,r=1;
	while(l<=r&&r<=n)
	{
		if(a[r]-a[l]<=k)//合法就推进右端点
		{
			ans=max(ans,r-l+1);//先更新答案,再推进端点 
			r++;
		} 
		else//不合法就推进左端点,减少差值 
		{
			l++;
		}
	}
	cout<<ans;
	return 0;
}
2020/10/5 21:29
加载中...