题解 | 空调遥控
空调遥控
https://www.nowcoder.com/practice/7cb58d56b30c4280ac07ae4428022e03
考虑二分查找，枚举a[i]，贪心地找到第一个大于a[i] + p * 2的下标j，max(j - i)就是答案。
#include <iostream>
#include <vector>
#include <algorithm>
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
int n, p;
std::cin >> n >> p;
std::vector<int> a(n);
for(int i = 0; i < n; i++){
std::cin >> a[i];
}
std::sort(a.begin(), a.end());
int ans = 0;
for(int i = 0; i < n; i++){
int j = std::upper_bound(a.begin() + i, a.end(), a[i] + p * 2) - a.begin();
ans = std::max(ans, j - i);
}
std::cout << ans << "\n";
return 0;
}