有 \(n\) 个值，分别为 \(a_1, a_2, \cdots, a_n\) 。希望做两个操作
- 移除一些（可能是 \(0\) 个）问题
- 重排列剩下的问题
一组值是好的当且仅当任意对于 \(\forall i, j,\ 1 \leq i,j \leq n,\ |i - j| = 1,\ s.t.\ |a_i - a_j| \leq k\) 。
已知 \(k\) ，使这组问题是好的，应至少移除多少问题。
（\(cf\) 的低分思维题真的很难，仅仅只是很好猜。现场绝大多人都是无脑用典、大力贪心即可猜过。）
仔细证明会发现其实是一个不错的题。
此题的典：当数组不强调顺序，且讨论绝对值。排序可忽视绝对值影响，且不影响结果。
有序数组性质：
性质：数组有序时，对应差分数组的最大的值最小。
- 证明：数组有序时，对于一个数 \(a_x\) ，它与另一个数的差分不超过为 \(a_{x} - a_{x - 1}\) 。
观察一：至少删去数，可以转化为至多存在数。问题转化为这些数的最大差分最小。
观察二：数组有序条件下，找出所有的 \(a_x,(a_x - a_{x - 1} > k)\) 删除，得到若干个区间。每个区间都是该区间构成的集合的极大答案。
于是找出剩下若干个区间中的最优答案。这是一个经典双指针可做的问题。
每个连续段满足性质 \(\forall i, s.t.\ a_i - a_{i - 1} \leq k\) 。
得到最大长度的差分数组后，加 \(1\) 即是最多存在数。它的补集大小即答案。
view
#include <bits/stdc++.h>
void solve() {
int n, k; std::cin >> n >> k;
std::vector<int> a(n+1);
for (int i = 1; i <= n; i++) std::cin >> a[i];
std::sort(a.begin() + 1, a.end());
int ans = 0;
for (int i = 2; i <= n; i++) {
int j = i;
if (a[j] - a[j - 1] > k) continue; // 区间大小为 0
while (j <= n && a[j] - a[j - 1] <= k) j++;
j -= 1;
ans = std::max(ans, j - i + 1);
i = j;
}
std::cout << n - (ans + 1) << '\n';
}
signed main() {
int _ = 1; std::cin >> _;
while (_--) { solve(); }
return 0;
}