1
Codeforces Round 886 (Div. 4) D. Balanced Round
https://codeforces.com/contest/1850/problem/D
题意
给出 t 组的 n,k,和一个数组a，可对数组a进行两种操作：
- 交换元素位置
- 删除元素
求使得数组a中每个元素之间的差值小于等于k，至少需要进行几次删除元素的操作。
实例
input
7
5 1
1 2 4 5 6
1 2
10
8 3
17 3 1 20 12 5 17 12
4 2
2 4 6 8
5 3
2 3 19 10 8
3 4
1 10 5
8 1
8 3 1 4 5 10 7 3
output
2
0
5
0
3
1
4
思路
排序后，问题=>求n-最大连续子序列l。
相邻两数之间大于k的两个元素之间，相当于是两个子串的分割线，根据题意知每个子串是不存在公共的元素。
可以用cou记录每个子串的长度，遇到分割线(相邻两元素>k)重新计数，最后去所有子串长度的最大值ans。
代码
#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define all(v) v.begin(), v.end()
#define rall(v) v.end(), v.begin()
#define pd push_back
#define sz(a) (int)a.size()
void solve(){
int n, k; cin>>n>>k;
vector<int> v(n);
for(int i=0;i<n;++i) cin>>v[i];
sort(all(v));
int cou = 1, ans = 1;
for(int i=1;i<n;++i){
if(v[i] - v[i-1] > k) cou = 1;
else ++cou;
ans = max(ans, cou);
}
cout << n - ans << '\n';
}
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int t;
cin>>t;
while(t--){
solve();
}
return 0;
}