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;
}