---

D. Balanced Round

原创 已于 2023-08-12 02:00:55 修改 · 粉丝可见 · 260 阅读 · 0 · 0 · 本内容遵循CC 4.0 BY-SA版权协议 版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。 · 编辑
文章链接：https://blog.csdn.net/hacker_51/article/details/132199663

题目：

cobol<br/>7<br/>5 1<br/>1 2 4 5 6<br/>1 2<br/>10<br/>8 3<br/>17 3 1 20 12 5 17 12<br/>4 2<br/>2 4 6 8<br/>5 3<br/>2 3 19 10 8<br/>3 4<br/>1 10 5<br/>8 1<br/>8 3 1 4 5 10 7 3<br/>

cobol<br/>2<br/>0<br/>5<br/>0<br/>3<br/>1<br/>4<br/>

思路：

题目意思是，输出最少删除多少个 不符合 两个数之间差 <= k 的元素，使它们的排列各元素之间的差值 <= k

这里是贪心排序，我们可以先从小到大排好序，使它们的差值尽可能的缩小，如何再遍历一遍找出符合 两个数之间差 <= k 的元素 数量是多少， 之后我们再 用总数量减去那他们符合两个数之间差 <= k 的元素 最长连续数量，就是我们要删除的最少元素数量

代码详解如下：

#include <iostream>
#include <vector>
#include <algorithm>
#define All(x) x.begin(),x.end()
#define endl '\n'
#define ___G std::ios::sync_with_stdio(false),cin.tie(0), cout.tie(0)
using namespace std;

inline void solve()
{
	vector<int>ans, a;
	int n, k;
	cin >> n >> k;
	for (int i = 0, num; i < n; ++i)
	{
		cin >> num;
		a.emplace_back(num);
	}

	sort(All(a));	// 排序，是它们的难度差尽可能缩小

	// cnt 用来计数，记录符合 a[i] - a[i - 1] <= k 的数量
	int cnt = 1;
	// 因为当前下标也是算是一个数值 所以 cnt 从 1 开始计数

	for (int i = 1; i < n; ++i)
	{
		// 如果大于记录的数值 碰到 大于 k 的情况，存储好
		// 满足 a[i] - a[i - 1] <= k 的数量
		if (a[i] - a[i - 1] > k)
		{
			ans.emplace_back(cnt);
			cnt = 1;
		}
		else
			cnt++;
	}

	// 因为有可能都可以满足
	// 所以 最后也要添加一下满足的数量
	ans.emplace_back(cnt);

	int maxs = -1;	// 变量 maxs 为满足 a[i] - a[i - 1] <= k 的数量

	// 找出 满足的最大数量
	for (auto i : ans)
	{
		maxs = max(maxs, i);
	}

	// 输出删除的最小数量
	cout << n - maxs << endl;

	return ;
}

int main()
{
	___G;
	int __t;
	cin >> __t;
	while (__t--)
	{
		solve();
	}
	return 0;
}

最后提交：