题解 | 空调遥控

考虑二分查找，枚举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;
}