Reach-Top OJ

问题 5969 --平衡难度

5969: 平衡难度★★

时间限制: 1 Sec 内存限制: 128 MB
提交: 30 解决: 17
[提交][状态][命题人:]

暑假马上要结束了，Reach-Top准备对全体学员进行一次小测试，以检查学员假期学习情况，并奖励优秀学员。作为Reach-Top的资深培训导师，出题任务就交给你了。为此，你准备了n个问题，问题i的难度系数为a_i。为了使得问题难度能够满足所有学员的检测需求，你可以执行以下操作:

（1）从问题列表中删除一些(可能为零个)问题;

（2）你可以按照你希望的任意顺序重新排列剩下的问题；

当且仅当任意两个连续问题的难度系数差的绝对值不超过k(小于或等于k)时，该问题列表可以被认为是难度平衡的，可以满足测试需要。

请问，你至少需要从问题列表中删除多少个问题才能够使得问题列表达到难度平衡？

第一行一个整数t(1≤t≤1000)：测试用例数；

每个测试用例两行：

第一行两个整数n（1≤n≤2e5）和k（1≤k≤1e9）：n为初始问题数量，k为任意两个连续问题的难度系数差的绝对值上限（即: |a_i+1 - a_i|<=k）；

第二行为n个整数a₁,a₂,a₃,……,a_i,……,a_n（1≤a_i≤1e9）：n个问题的难度系数;

输入数据确保，所有测试样例的n之和不超过2e5;

共t行，每个测试用例一行一个整数：最少需要从问题列表中删除的问题的数量。

样例输入

Copy

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

样例输出

Copy

在第一个测试用例中，可以选择删除问题1和问题2，剩下三个问题的难度为：[4,5,6],满足|5-4|=1<=1, |6-5]=1<=1，即剩下三个问题可以构成平衡难度问题列表。因此，删除问题的最少数量为2个；

在第二个测试用例中，只有一个问题，已经满足要求，删除问题数量为0个；