CF1832B Maximum Sum

给定一个数组 $a_1, a_2, \dots, a_n$，其中所有元素互不相同。 你需要对该数组恰好进行 $k$ 次操作。每次操作，你可以选择以下两种操作之一（任选其一）： - 找出数组中最小的两个元素，并将它们删除； - 找出数组中的最大元素，并将其删除。 请你计算操作结束后，数组中剩余元素的最大可能和。

第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。 每个测试用例包含两行： - 第一行包含两个整数 $n$ 和 $k$（$3 \le n \le 2 \cdot 10^5$；$1 \le k \le 99999$；$2k < n$），分别表示数组元素个数和操作次数。 - 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^9$，所有 $a_i$ 互不相同），表示数组的元素。 输入还满足一个额外条件：所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

对于每个测试用例，输出一个整数，表示操作结束后数组中剩余元素的最大可能和。

在第一个测试用例中，执行第一次操作后的结果如下： - 两个最小值为 $1$ 和 $2$，删除它们后数组变为 $[5, 10, 6]$，其和为 $21$； - 最大值为 $10$，删除它后数组变为 $[2, 5, 1, 6]$，其和为 $14$。 $21$ 是最优答案。 在第二个测试用例中，最优策略是先删除两个最小值，再删除一个最大值。 由 ChatGPT 4.1 翻译