传感器是一种将物理量转变为数字信号的电子元件。虽然传感器能比较准确地测试出某物理量,但很可能出现随机误差。研究员小南在某次实验中,用两个不同的传感器同时对同一个变量进行了 $$$n$$$ 个单位时间的观测,得到了一些实验数据。两传感器的读数并不完全相同,但大致趋势是统一的。所以小南希望尽可能地将两段读数关联起来,看看能不能得到更准确的结果。
为此,小南制定了如下方案。假设有传感器 $$$A$$$ 和 $$$B$$$,它们每间隔单位时间采样得到一个整数,设在第 $$$i$$$ 时间,$$$A$$$、$$$B$$$ 两传感器的读数分别为 $$$x_A^{(i)}$$$ 和 $$$x_B^{(i)}$$$。
由于不想浪费数据,所以小南要求每个 $$$A$$$ 传感器的数据要对应一个或多个 $$$B$$$ 传感器的数据,$$$B$$$ 传感器的每个数据也要对应一个或多个 $$$A$$$ 传感器的数据。
另外,因为数据有时序性,所以,如果 $$$x_A^{(i)}$$$ 与 $$$x_B^{(j)}$$$ 匹配,则对任意的 $$$a \gt i, b \lt j$$$,$$$x_A^{(a)}$$$ 与 $$$x_B^{(b)}$$$ 不能匹配;对称地,对任意的 $$$c \lt i, d \gt j$$$,$$$x_A^{(c)}$$$ 与 $$$x_B^{(d)}$$$ 也不能匹配。
以下反例中,虚线部分为错误连线,因为产生了交叉。
该样例的正确连线如下
定义建立了匹配的一组读数的距离为读数之差的绝对值,即 $$$\mathrm{dist}(i, j) = \left|x_A^{(i)} - x_B^{(j)}\right|$$$。距离越小,说明关联程度越高。
小南希望能在满足条件的情况下,最小化整个匹配的距离之和,并得到这个距离之和。
第一行一个整数 $$$T$$$,表示测试用例组数。
对于每一组测试样例:
数据范围:$$$1 \le T \le 200$$$,$$$1 \le n \le 1000$$$,$$$-100 \le x \le 100$$$。
注意:输入数据中存在纯随机的数据,这种情况不需要特殊处理,只需要按照题面中的要求输出结果,小南看到一个大得不得了的数字会考虑换一对传感器。
对于每个测试用例,输出一行,该行仅有一个整数,为最小的距离。
3 5 1 2 3 4 5 1 3 4 2 5 5 1 2 -2 1 9 3 2 -4 1 7 7 1 2 -2 1 9 1 1 3 2 -4 1 7 9 9
3 6 22
| Название |
|---|


