尺取り法を使ってこの問題を解きます。

• 前準備として、 \(X\) を昇順にソートします。
• \(r=1,2,\dots,N\) について、以下の問題を解きます。
  • 座標 \(X_l,X_{l+1},\dots,X_r\) にある木を全てカバーできるような最小の \(l\) はいくつか？
  • この問題は、 \(X_r-X_l > K\) となっている限り \(l\) を増やし続けることで解くことができます。
  • 最適解は、 \(r-l+1\) としてありうる最大値となります。
  • \(r\) を増やしていくとき、この問題の答えの \(l\) が小さくならないことから尺取り法が適用可能です。具体的には、 \(r+1\) の求解を始める際に \(r\) に対しての \(l\) の解から始めることで、全体で \(l\) に対する加算を最大 \(N\) 回で済ませることができます。

時間計算量は \(O(N \log N)\) です(ソートがボトルネックになります)

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;

int main(){
  int N,K;
  cin >> N >> K;
  vector<int> X(N);
  for(auto &nx : X){cin >> nx;}
  sort(X.begin(),X.end());
  int l=0,res=0;
  for(int r=0;r<N;r++){
    while(X[r]-X[l]>K){l++;}
    res=max(res,r-l+1);
  }
  cout << res << "\n";
  return 0;
}