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

热门相关：总裁别再玩了   上神来了   上神来了   上神来了   戏精老公今天作死没