← 返回题目列表

Codeforces · 1585/C

C. 最小化距离

中文机器翻译题面 查看原题

总共 $$$n$$$ 个仓库位于数轴上。仓库 $$$i$$$ 位于 $$$x_i$$$ 点,$$$1 \le i \le n$$$。

您是一名推销员,拥有 $$$n$$$ 袋货物,试图将一袋货物运送到每个 $$$n$$$ 仓库。您和 $$$n$$$ 行李最初位于原点 $$$0$$$。您一次最多可携带 $$$k$$$ 行李。您必须从始发地收集所需数量的货物,并将其运送到各自的仓库,然后返回始发地提取您的下一批货物。

计算将所有货物袋运送到仓库所需的最短距离。交付所有行李后,您无需返回出发地。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10\,500$$$)。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le k \le n \le 2 \cdot 10^5$$$)。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$x_1, x_2, \ldots, x_n$$$ ($$$-10^9 \le x_i \le 10^9$$$)。一些仓库可能具有相同的位置。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出一个整数,表示将所有货物袋运送到仓库所需的最小距离。

示例

输入 #1

4
5 1
1 2 3 4 5
9 3
-5 -10 -15 6 5 8 3 7 4
5 3
2 2 3 3 3
4 2
1000000000 1000000000 1000000000 1000000000

输出 #1

25
41
7
3000000000

注意

在第一个测试用例中,您一次只能携带一个包。因此,以下是给出最小行进距离的解序列: $$$0 \to 2 \to 0 \to 4 \to 0 \to 3 \to 0 \to 1 \to 0 \to 5$$$,其中每个 $$$0$$$ 表示您前往原点并抓取一个袋子,每个正整数表示您将袋子运送到该坐标处的仓库,总距离为 $$$25$$$ 单位。必须注意的是,还有其他序列给出相同的距离。

在第二个测试用例中,您可以在多个此类序列中遵循以下序列来移动最小距离:$$$0 \to 6 \to 8 \to 7 \to 0 \to 5 \to 4 \to 3 \to 0 \to (-5) \to (-10) \to (-15)$$$,距离为 $$$41$$$。可以看出,$$$41$$$ 是该测试用例的最佳距离。