80分求助~
查看原帖
80分求助~
682342
zzzcdq楼主2022/4/15 20:27

各位大佬拔刀相助帮忙看一下,80分,双指针做法

#include <iostream>
#include <algorithm>
using namespace std;
int n,k,i,j,ans,a[50010],f[50010][2];
int main()
{
	cin >> n >> k;
	for(i = 1;i <= n;i ++) cin >> a[i];
	sort(a + 1,a + n + 1);
	i = j = 1;
	while(1)
	{
		if(i > n || j > n) break;
		if(a[j] - a[i] > k)
		{
			f[i][0] = max(f[i][0],j - i);
			f[j - 1][1] = max(f[j - 1][1],j - i);
			i ++;
		}
		else j ++;
	}
	for(i = 1;i <= n;i ++) f[i][1] = max(f[i][1],f[i - 1][1]);
	for(i = n;i >= 1;i --) f[i][0] = max(f[i][0],f[i + 1][0]);
	for(int i = 1;i <= n;i ++) ans = max(ans,f[i][1] + f[i + 1][0]);
	cout << ans << endl;
	return 0;
}

谢谢大佬

2022/4/15 20:27
加载中...