空调遥控_牛客博客

分析题目给的式子 $∣ a_{i} - k ∣ < = p$ ，我们化简之后这个式子可以变化成 $a_{i} - p < = k < = a_{i} + p$ ，题目的意思就是要找 $k$ 为某一值时候最多进入训练状态的人。根据那个式子，我们可以把每个 $a_{i}$ 都可以对应一个范围使得 $k$ 取整个范围中的任一值都能让 $第 i$ 个人进入训练状态。 $\\$ 根据这个式子我们可以很显然的发现可以利用差分的思想，每次确定一个范围，最后前缀和找最大值即可,当然左边界有可能是负数，所以我们要特判一下，如果 $< = 0$ ，我们就默认左边界是1，范围就是枚举 $2 * 1 0^{6}$ 的前缀和。

#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
# include<iostream>
# include<iomanip>
# include<algorithm>
# include<cmath>
# include<cstdio>
# include<set>
# include<stack>
# include<queue> 
# include<map>
# include<string>
# include<cstring> 


# define eps 1e-9
# define fi first
# define se second
# define ll long long
# define int ll
// cout<<fixed<<setprecision(n) 
using namespace std;
   
typedef unsigned long long ull;
typedef pair<int,int > PII; 
const int mod=1e9+7;
const int MAX=3e6+10;
const int Time=86400;
const int X=131;
const int inf=0x3f3f3f3f;
const double PI = 1e-4;
double pai = 3.14159265358979323846; 

int n,p,a[MAX],ans;
int s[MAX];


signed main(){  
    std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin >> n >> p;
    for(int i = 0 ; i < n ; i ++ ){
		cin >> a[i];
		if(a[i] - p >= 1) s[a[i] - p]++;
		 else s[1]++;
		s[a[i] + p + 1]--;
	}
    for(int i = 1 ; i <= 2000005 ; i ++ ){
		s[i]+=s[i-1];
		ans = max(ans,s[i]);
	}
	cout<<ans;
    return 0; 
}
/*
1 1 2 3 5 8 13  
*/