CF1904C Array Game

给定一个包含 $n$ 个正整数的数组 $a$。每次操作，你可以选择一对 $(i, j)$，满足 $1\leq i < j\leq |a|$，并将 $|a_i - a_j|$ 添加到数组 $a$ 的末尾（即 $n$ 增加 $1$，并令 $a_n = |a_i - a_j|$）。你的任务是经过 $k$ 次操作后，最小化并输出数组 $a$ 的最小值。

每个测试点包含多组测试用例。第一行包含一个整数 $t$（$1 \leq t \leq 1000$），表示测试用例的数量。 每个测试用例的第一行包含两个整数 $n$ 和 $k$（$2\le n\le 2\cdot 10^3$，$1\le k\le 10^9$），分别表示数组的长度和你需要进行的操作次数。 每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1\le a_i\le 10^{18}$），表示数组 $a$ 的元素。 保证所有测试用例中 $n^2$ 的和不超过 $4\cdot 10^6$。

对于每个测试用例，输出一个整数，表示经过 $k$ 次操作后，数组 $a$ 的最小可能值。

在第一个测试用例中，经过任意 $k=2$ 次操作后，$a$ 的最小值都将为 $1$。 在第二个测试用例中，一种最优策略是先选择 $i=1, j=2$，将 $|a_1 - a_2| = 3$ 添加到 $a$ 的末尾，此时 $a=[7, 4, 15, 12, 3]$。然后选择 $i=3, j=4$，将 $|a_3 - a_4| = 3$ 添加到 $a$ 的末尾，此时 $a=[7, 4, 15, 12, 3, 3]$。最后一次操作选择 $i=5, j=6$，将 $|a_5 - a_6| = 0$ 添加到 $a$ 的末尾。此时 $a$ 的最小值为 $0$。 在第三个测试用例中，一种最优策略是先选择 $i=2, j=3$，将 $|a_2 - a_3| = 3$ 添加到 $a$ 的末尾。无论第二次操作如何，$a$ 的最小值都不会小于 $3$。 由 ChatGPT 4.1 翻译