CF1618D Array and Operations

给定一个包含 $n$ 个整数的数组 $a$，以及另一个整数 $k$，满足 $2k \le n$。 你需要对该数组恰好进行 $k$ 次操作。每次操作，你需要选择数组中的两个元素（记为 $a_i$ 和 $a_j$，它们可以相等也可以不同，但在数组中的位置必须不同），将它们从数组中移除，并将 $\lfloor \frac{a_i}{a_j} \rfloor$ 加到你的得分上，其中 $\lfloor \frac{x}{y} \rfloor$ 表示不超过 $\frac{x}{y}$ 的最大整数。 初始时，你的得分为 $0$。在你恰好进行了 $k$ 次操作后，将数组中剩余的所有元素加到得分上。 请计算你可能获得的最小得分。

输入的第一行包含一个整数 $t$（$1 \le t \le 500$），表示测试用例的数量。 每个测试用例包含两行。第一行包含两个整数 $n$ 和 $k$（$1 \le n \le 100$；$0 \le k \le \lfloor \frac{n}{2} \rfloor$）。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 2 \times 10^5$）。

输出一个整数，表示你可能获得的最小得分。

我们来看样例测试。 在第一个测试用例中，一种获得分数 $2$ 的方法如下： 1. 选择 $a_7 = 1$ 和 $a_4 = 2$ 进行操作，得分变为 $0 + \lfloor \frac{1}{2} \rfloor = 0$，数组变为 $[1, 1, 1, 1, 3]$； 2. 选择 $a_1 = 1$ 和 $a_5 = 3$ 进行操作，得分变为 $0 + \lfloor \frac{1}{3} \rfloor = 0$，数组变为 $[1, 1, 1]$； 3. 选择 $a_1 = 1$ 和 $a_2 = 1$ 进行操作，得分变为 $0 + \lfloor \frac{1}{1} \rfloor = 1$，数组变为 $[1]$； 4. 将剩余的元素 $1$ 加入得分，最终得分为 $2$。 在第二个测试用例中，无论你选择怎样的操作，最终得分都是 $16$。 在第三个测试用例中，一种获得分数 $0$ 的方法如下： 1. 选择 $a_1 = 1$ 和 $a_2 = 3$ 进行操作，得分变为 $0 + \lfloor \frac{1}{3} \rfloor = 0$，数组变为 $[3, 7]$； 2. 选择 $a_1 = 3$ 和 $a_2 = 7$ 进行操作，得分变为 $0 + \lfloor \frac{3}{7} \rfloor = 0$，数组变为空； 3. 数组为空，得分不再变化。 在第四个测试用例中，无法进行任何操作，因此得分为数组元素之和：$4 + 2 = 6$。 由 ChatGPT 4.1 翻译