310550: CF1850D. Balanced Round
Description
You are the author of a Codeforces round and have prepared $n$ problems you are going to set, problem $i$ having difficulty $a_i$. You will do the following process:
- remove some (possibly zero) problems from the list;
- rearrange the remaining problems in any order you wish.
A round is considered balanced if and only if the absolute difference between the difficulty of any two consecutive problems is at most $k$ (less or equal than $k$).
What is the minimum number of problems you have to remove so that an arrangement of problems is balanced?
InputThe first line contains a single integer $t$ ($1 \leq t \leq 1000$) — the number of test cases.
The first line of each test case contains two positive integers $n$ ($1 \leq n \leq 2 \cdot 10^5$) and $k$ ($1 \leq k \leq 10^9$) — the number of problems, and the maximum allowed absolute difference between consecutive problems.
The second line of each test case contains $n$ space-separated integers $a_i$ ($1 \leq a_i \leq 10^9$) — the difficulty of each problem.
Note that the sum of $n$ over all test cases doesn't exceed $2 \cdot 10^5$.
OutputFor each test case, output a single integer — the minimum number of problems you have to remove so that an arrangement of problems is balanced.
ExampleInput7 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 3Output
2 0 5 0 3 1 4Note
For the first test case, we can remove the first $2$ problems and construct a set using problems with the difficulties $[4, 5, 6]$, with difficulties between adjacent problems equal to $|5 - 4| = 1 \leq 1$ and $|6 - 5| = 1 \leq 1$.
For the second test case, we can take the single problem and compose a round using the problem with difficulty $10$.
Input
题意翻译
# **题目描述** 你是codeforces round的出题人，现在你将设置n个问题，第i个问题的难度是ai。你将进行以下操作步骤： 1. 从题单中移除一部分题目（移除的题目的数量可能是0） 2. 按你想要的任何顺序重新排列剩余的问题 当且仅当任意两道连续的题目的难度之差的绝对值最多为k时（即绝对值小于等于k），这一回合（round）会被认为是平衡的。 你最少需要移除多少道题目，才能使问题的安排是平衡的？ ## 输入格式 第一行包含一个整数t(1≤t≤1000)，代表样例的数量 对于每个样例的第一行包含两个正整数n(1≤n≤2⋅10^5)和k(1≤k≤10^9)，n代表初始问题的数量，k代表连续的两个问题难度之差的绝对值的最大值 对于每个样例的第二行包含n个用空格隔开的整数ai(1≤ai≤10^9)，代表每个问题的难度 请注意，所有测试用例的n不超过2⋅10^5 ## 输出格式 对于每个测试用例，输出一个正整数，代表你为了使问题的安排平衡所最少需要移除的问题的数量 ### 说明/提示 对于第一个样例，我们可以移除前两个问题并得到一个问题的排列，其难度为【4，5，6】，连续的两个问题的难度之差的绝对值满足|5-4|=1≤1，|6-5|=1≤1 对于第二个样例，我们可以得到一个问题并将这一个问题（难度10）作为一个回合(round)Output
你是一个Codeforces比赛的出题人，你准备了n道题目，每道题目的难度为a_i。你可以进行以下过程：
- 从列表中删除一些（可能为零）题目；
- 以任何你希望的顺序重新排列剩余的题目。
如果任意两个连续题目的难度之差的绝对值最多为k（小于或等于k），则该比赛被认为是“平衡的”。
问：你至少需要删除多少道题目，才能使题目排列平衡？
输入数据格式：
第一行包含一个整数t（1≤t≤1000）——测试用例的数量。
每个测试用例的第一行包含两个正整数n（1≤n≤2×10^5）和k（1≤k≤10^9）——题目的数量和连续题目之间允许的最大绝对难度差。
每个测试用例的第二行包含n个空格分隔的整数a_i（1≤a_i≤10^9）——每道题目的难度。
注意，所有测试用例的n之和不超过2×10^5。
输出数据格式：
对于每个测试用例，输出一个整数——为了使题目排列平衡，你至少需要删除的题目数量。
示例：
输入：
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
输出：
2
0
5
0
3
1
4
注意：
在第一个测试用例中，我们可以删除前两道题目，并使用难度为[4, 5, 6]的题目构建一个集合，相邻题目之间的难度等于|5-4|=1≤1和|6-5|=1≤1。
在第二个测试用例中，我们可以取难度为10的单个题目，并使用该题目构建一个比赛。题目大意： 你是一个Codeforces比赛的出题人，你准备了n道题目，每道题目的难度为a_i。你可以进行以下过程： - 从列表中删除一些（可能为零）题目； - 以任何你希望的顺序重新排列剩余的题目。 如果任意两个连续题目的难度之差的绝对值最多为k（小于或等于k），则该比赛被认为是“平衡的”。 问：你至少需要删除多少道题目，才能使题目排列平衡？ 输入数据格式： 第一行包含一个整数t（1≤t≤1000）——测试用例的数量。 每个测试用例的第一行包含两个正整数n（1≤n≤2×10^5）和k（1≤k≤10^9）——题目的数量和连续题目之间允许的最大绝对难度差。 每个测试用例的第二行包含n个空格分隔的整数a_i（1≤a_i≤10^9）——每道题目的难度。 注意，所有测试用例的n之和不超过2×10^5。 输出数据格式： 对于每个测试用例，输出一个整数——为了使题目排列平衡，你至少需要删除的题目数量。 示例： 输入： 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 输出： 2 0 5 0 3 1 4 注意： 在第一个测试用例中，我们可以删除前两道题目，并使用难度为[4, 5, 6]的题目构建一个集合，相邻题目之间的难度等于|5-4|=1≤1和|6-5|=1≤1。 在第二个测试用例中，我们可以取难度为10的单个题目，并使用该题目构建一个比赛。