题解 P3143 【[USACO16OPEN]Diamond Collector S】

排序 + 2-pointer 做法

思路

先排序。

然后我们以两个指针分别从最左端和最右端开始扫，分别记录两端的最大值，从最左端开始扫记录每一个点的左端最大的差小于等于 k 的序列，而从最右端开始扫则记录的是每一个点的右端最大的差小于等于 k 的序列。这样处理之后，在一遍枚举所有的点，对他两端的状态进行求和，得到的便是最终的答案，即$ ans = max(ans,ansl(i)+ansl(i+1)) $ ，在这之中为了避免重复计算一个点的值，我们要加和的是 i 和 i+1。

code

#include <cstdio>
#include <algorithm>
#define sf(x) scanf("%d",&x)
#define pf(x) printf("%d\n",x)
#define N 50077
using namespace std;

int n,k;
int a[N],ansl[N],ansr[N];

int main(){
	sf(n),sf(k);
	for(int i=1;i<=n;++i) sf(a[i]);
	sort(a+1,a+n+1);
	int l=1,r=n;
	for(int i=1;i<=n;++i){
		while(a[i]-a[l]>k&&l<=i) l++;
		ansl[i]=max(ansl[i-1],i-l+1);
	}
	for(int i=n;i>=1;--i){
		while(a[r]-a[i]>k&&r>=i) r--;
		ansr[i]=max(ansr[i+1],r-i+1);
	}
	int ans=0;
	for(int i=1;i<n;++i)
		ans=max(ans,ansl[i]+ansr[i+1]);
	pf(ans);	
}