AcWing 1822. 钻石收藏家
原题链接
简单
作者:
王不语
,
2022-01-26 13:22:27
,
所有人可见
,
阅读 262
C++ 代码
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int main()
{
int n, k; cin >> n >> k;
vector<int> v(n), a(n), b(n + 1); // v数组记录数据
for(int i = 0;i < n;i ++) scanf("%d", &v[i]);
sort(v.begin(), v.end());
//预处理1:a[i]记录从i开始到v[i] + k的下标 那么a[i] - i即为个数
for(int i = 0;i < n;i ++)
a[i] = upper_bound(v.begin(), v.end(), v[i] + k) - v.begin();
//预处理2:b[i]记录从i开始到最后 个数的最大值
int mx = 0;
for(int i = n - 1;i >= 0;i --)
{
mx = max(mx, a[i] - i);
b[i] = mx;
}
b[n] = 0; // 多加一个防止数组越界
int ans = 0;
for(int i = 0;i < n;i ++)
{
int l = i;
int r = upper_bound(v.begin(), v.end(), v[l] + k) - v.begin(); // r - 1是实际位置
ans = max(ans, r - l + b[r]); // 找到l和r后答案即为r - l + b[r]的最大值
if(r == n) break; // b[r]就是从r开始后面区间的最大值
}
cout << ans << endl;
return 0;
}