CF1591C Minimize Distance

共有 $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$。

对于每组测试用例，输出一个整数，表示将所有货物送达各仓库所需经过的最小距离。

在第一个测试用例中，你每次只能携带一袋货物。因此，以下是一种最小总路程的送货顺序：$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$ 是该测试用例的最优解。 由 ChatGPT 4.1 翻译