void solve()
{
	int n, k;
	cin >> n >> k;
	int ai[n+1];
	for(int i = 1;i <= n; i++)	cin >> ai[i];
	sort(ai+1,ai+1+n);//使用冒泡排序即可
	int ans = 0, sum = 0;//sum为符合条件的子段长度
	for(int i = 2;i <= n; i++){
		if(ai[i]-ai[i-1]<=k){
			 sum++;
		}
		else{
			ans = max(ans,sum);//找出最长串
			sum = 0;//不符合条件sum重置
		}
	}
	ans = max(ans,sum);//ans为最长子段
	cout << n-ans-1 << "\n";
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int _ = 1;
	cin >> _;
	while(_--){
		solve();
	}
	return 0;
}

这题也很简单,根据题目,既然可以排序,那么咱们不妨从开始就进行排序;咱们可以这样想,如果a[i]-a[i-1]>k的话那么a[i+p]-a[i]也必然大于k,同理a[i]-a[i-1-p]也必然大于k;(p>=1) 经过以上分析,很容易发现,这题答案很明显就是求最大子段的,那么就可以有如下答案:

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin>>t;
    while(t--){
        int n,k;
        cin>>n>>k;
        vector <int> a(n+1,0),dp(n,0);
        for(int i = 1;i<=n;i++) cin>>a[i];
        sort(a.begin()+1,a.end());//首先排序
        int l = 1;//定义左端
        for(int i = 2;i<=n;i++){
            if(a[i]-a[i-1]>k){
                 
                dp[l] = i-l;//其实不用思考为什么是dp[l],毕竟下面还是要排序的,这里只是记录一下
                l = i;//根据分析,就要重新求子段了,因此l=i;
                
            }
        }
        dp[n-1] = n - l+1;//最后的子段不要忘记了
//这里下标也是随便取的(不要和原来的重了),但是不要出现段错误(修了好长时间bug)

        sort(dp.begin(),dp.end());//排序后只要取最大的子段,然后数字个数减去最大子段就是最小的答案了
        cout<<n-dp.back()<<endl;
    }
    
//1 2 4 5 6
/*多说无益,上示例,开始时l = 1,i = 2
当i = 3时,显然不符合题意,那么第一个子段dp长度诞生等于2;然后更新子段左端l=i;
一直到结束都是符合题意的,因此不要忘记最后的子段dp等于5-3+1=3;
然后dp排序找出最大子段,用总个数减去最大子段,就是最小个数*/
}

核心思路：要让删除的天数最少，需保留尽可能多的天数。最优策略是将数组排序（排序后相邻元素差值最小，能最大化满足条件的连续天数），然后找到排序后数组中最长的连续子数组（其中相邻元素的绝对差≤k）—— 因为排序后该子数组可直接按顺序排列，满足 “任意连续两天差值≤k” 的条件。最终最少删除天数 = 总天数 n - 最长满足条件的子数组长度。