Can you solve this question?

Правка en1, от Invn1234, 2023-07-22 17:58:09

D. Balanced Round time limit per test2 seconds memory limit per test256 megabytes inputstandard input outputstandard output You are the author of a Codeforces round and have prepared n problems you are going to set, problem i having difficulty ai . 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?

Input The first line contains a single integer t — the number of test cases.

The first line of each test case contains two positive integers n and k — 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] — the difficulty of each problem.

Note that the sum of n over all test cases doesn't exceed 2⋅105 .

Output For each test case, output a single integer — the minimum number of problems you have to remove so that an arrangement of problems is balanced. Example Input: 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

Output: 2 0 5 0 3 1 4

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский Invn1234 2023-07-22 17:58:09 1480 Initial revision (published)