【PR #12】电塔 - 题目

今天是 YQH 的生日，她得到了一套益智玩具—— $n$ 个电塔作为生日礼物。所有电塔位于同一条直线上。具体的，把电塔所在直线抽象为一条数轴的非负半轴，那么第 $i$ 个电塔位于数轴上 $x_i$ 的位置。

假如两个电塔之间的相对距离严格小于 $d$，那么它们就会放电。在游玩一段时间后，YQH 感到厌倦了，于是她准备把这些电塔收拾起来。为了不浪费电，她希望把电塔调到都不放电的状态。

具体的，YQH 每次可以把某个电塔沿数轴正方向移动一个单位或沿数轴负方向移动一个单位，但是必须保证电塔位于数轴的非负半轴。你可以认为其他电塔不会干扰电塔的移动。

移动电塔是一个很累的行为，所以 YQH 希望求出移动电塔的最小次数，使得所有电塔都不放电。

本题采用多组测试，第一行一个整数 $T$ 表示数据组数。

对于每组数据：

第一行两个正整数 $n,d$。

第二行 $n$ 个非负整数 $x_i$，表示电塔的位置。

对于每组数据，输出一行一个整数表示答案。

6
16

对于第一组数据，考虑电塔最终的位置 $x^\prime=[0,1,2,3]$，显然满足全部电塔不放电的要求，移动次数为 $\sum|x_i-x^\prime_i|=6$，可以证明没有更优的解。

对于第二组数据，考虑电塔最终的位置 $x^\prime=[0,100,20,10]$，移动次数为 $\sum|x_i-x^\prime_i|=16$，可以证明没有更优的解。

见下发文件中 ex_ele2.in 和 ex_ele2.ans。

见下发文件中 ex_ele3.in 和 ex_ele3.ans。

对于全部数据，保证 $1\le T\le 10^5,1\le n\le 2\times 10^5,1\le d\le 10^6,0\le x_i\le 3\times 10^{11},\sum n\le 10^6$。

$\text{subtask1 20pts}$，$n\le 10,x_i\le 1000,T=1$。

$\text{subtask2 20pts}$，$d=1$。

$\text{subtask3 10pts}$，$n\le 200,T\le 5$。

$\text{subtask4 20pts}$，$n\le 2000,T\le 5$。

$\text{subtask5 30pts}$，无特殊限制。

时间限制：$\texttt{2s}$

空间限制：$\texttt{512MB}$

Public Judge