Balanced Round 题解
原题链接。
题目大意
给你一些数，问至少删掉多少数后两两不大于 k。
我们可以画图理解。
最后我们取 max(2,1)，由于我们求的是合法的，所以还得用长度减去 2，最终答案就是 2。
根据图我们就知道可以遍历一遍数组，用 t 记录下最长合法序列长度，最后用 n - t 即可。
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
void work()
{
int a[N];
int n, k;
cin >> n >> k;
for(int i = 1;i <= n;i ++ ){
cin >> a[i];
}
sort(a + 1, a + 1 + n);
int maxn = 1;
for(int i = 2, t = 1;i <= n;i ++ ){
if(a[i] - a[i - 1] > k) t = 1;
else t ++;
maxn = max(maxn, t);
}
cout << n - maxn << endl;
}
int main()
{
int T;
cin >> T;
while(T -- ){
work();
}
return 0;
}