問題の条件を整理して簡単にしてみましょう.
問題原案:uni_kakurenbo
整数 についての条件 を考えます.
数直線をイメージするとよいです.
これは, を中央とした幅が の閉区間に が含まれることと等しいです.
整数 に対して, なる任意の整数 について が上記の条件を満たすような が存在する最大の整数 を とします.
を昇順に並び替えると, は に関して広義単調増加となりますから,尺取り法の要領で の昇順に を求めることができます.
このとき, の最大値が答えです.
解説:uni_kakurenbo
xxxxxxxxxx
using i32 = std::int32_t;
__attribute__((constructor)) inline void fast_io() { std::ios::sync_with_stdio(false), std::cin.tie(nullptr); }
i32 solve(i32, const i32 k, std::vector<i32>& a) {
std::sort(a.begin(), a.end());
std::ptrdiff_t ans = 0;
auto r = a.begin();
for(auto l=a.begin(); l<a.end(); ++l) {
while(r != a.end() and *r - *l <= 2*k) r++;
ans = std::max(ans, r - l);
}
return ans;
}
signed main() {
i32 $; std::cin >> $;
while($--) {
i32 n, k; std::cin >> n >> k;
std::vector<i32> a(n); for(auto& v : a) std::cin >> v;
std::cout << solve(n, k, a) << "\n";
}
}
xxxxxxxxxx
for _ in range(int(input())):
n, k = map(int, input().split())
A = sorted(map(int, input().split()))
r, ans = 0, 0
for l in range(n):
while r != n and A[r] - A[l] <= 2*k:
r += 1
ans = max(ans, r - l)
print(ans)