题目内容

在音频后期处理中，有 $n$ 个音频片段，每个片段有一个整数音量值。给定一个干扰阈值 $d$，若两个片段的音量值之差的绝对值不超过 $d$，即 $|a_i - a_j| \le d$，则称这两个片段相互干扰。工程师可以执行任意次操作，每次操作选择一对片段并将它们同时删除（片段总数减少 $2$）。经过若干次操作后，要求最终剩余的片段中任意两个之间都不再相互干扰，并且希望保留的片段数量尽可能多。请你计算在最优操作下，最终能保留的最大片段数量。

约束条件：

• 测试数据组数 $T$ 不超过 $10^4$。
• 每组数据中，片段数量 $n$ 满足 $1 \le n \le 2 \times 10^5$。
• 干扰阈值 $d$ 满足 $0 \le d \le 10^9$。
• 每个音量值 $a_i$ 满足 $0 \le a_i \le 10^9$。
• 所有测试数据的 $n$ 之和不超过 $2 \times 10^5$。

输入描述

第一行包含一个整数 $T$，表示测试数据组数。接下来依次描述每组测试数据，对于每组数据： 第一行包含两个整数 $n$ 和 $d$，分别表示片段数量和干扰阈值。 第二行包含 $n$ 个整数，表示各个片段的音量值。

输出描述

对于每组测试数据，输出一行一个整数，表示最终能保留的最大片段数量。

样例1

输入

1
1 10
5

输出

1

说明

只有一个片段，不需要任何操作即可保留，且不存在其他片段与之干扰。最终保留 1 个。

样例2

输入

1
2 0
2 2

输出

0

说明

$d=0$，两个片段的音量值相同，差值 $|2-2|=0 \le 0$，相互干扰。只能将它们成对删除，最终保留 0 个。

样例3

输入

1
5 3
1 5 6 10 12

输出

3

说明

将音量值排序得 $[1,5,6,10,12]$。贪心选择不干扰的最大集合：保留 $1$；$5-1=4>3$，保留 $5$；$6-5=1\le3$，不保留；$10-5=5>3$，保留 $10$；$12-10=2\le3$，不保留。最大独立集大小 $M=3$。需要删除 $5-3=2$ 个片段，恰好可以成对删除，故最终保留 3 个。

样例4

输入

1
6 2
1 2 2 4 5 7

输出

2

说明

排序得 $[1,2,2,4,5,7]$。贪心选择：保留 $1$，跳过 $2,2$，保留 $4$，跳过 $5$，保留 $7$，得 $M=3$。此时需要删除 $6-3=3$ 个片段，但每次操作必须删除 2 个，无法完全成对删除。因此必须放弃一个保留的片段，使得删除数量变为偶数，最终保留 $M-1=2$ 个。

开通会员即可查看完整视频题解： 1.题目讲解 2.思路分析 3.逐行代码手写