CF1998C Perform Operations to Maximize Score

我看见了 satyam343。我在发抖。请这次多出一些中位数相关的问题。我太喜欢这些了。拜托了 satyam343，我们相信你。 —— satyam343 的头号粉丝 给定一个长度为 $n$ 的数组 $a$ 和一个整数 $k$。你还会得到一个长度为 $n$ 的二进制数组 $b$。 你最多可以进行 $k$ 次如下操作： - 选择一个下标 $i$（$1 \leq i \leq n$），且 $b_i = 1$。将 $a_i$ 增加 $1$（即 $a_i = a_i + 1$）。 你的得分定义为 $\max\limits_{i = 1}^{n} \left( a_i + \operatorname{median}(c_i) \right)$，其中 $c_i$ 表示将 $a_i$ 从 $a$ 中删除后得到的长度为 $n-1$ 的数组。换句话说，你的得分是所有 $a_i + \operatorname{median}(c_i)$ 中的最大值，$i$ 从 $1$ 到 $n$。 请你在最优地进行操作后，求出你能获得的最大得分。 对于任意数组 $p$，$\operatorname{median}(p)$ 定义为 $ \left\lfloor \frac{|p|+1}{2} \right\rfloor $ 小的元素。例如，$\operatorname{median}([3,2,1,3]) = 2$，$\operatorname{median}([6,2,4,5,1]) = 4$。

第一行包含一个整数 $t$（$1 \leq t \leq 10^4$），表示测试用例的数量。 每个测试用例的第一行包含两个整数 $n$ 和 $k$（$2 \leq n \leq 2 \cdot 10^5$，$0 \leq k \leq 10^9$），分别表示数组 $a$ 的长度和你可以进行的操作次数。 接下来一行包含 $n$ 个用空格分隔的整数 $a_1, a_2, \ldots, a_n$（$1 \leq a_i \leq 10^9$），表示数组 $a$。 接下来一行包含 $n$ 个用空格分隔的整数 $b_1, b_2, \ldots, b_n$（$b_i$ 为 $0$ 或 $1$），表示数组 $b$。 保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

对于每个测试用例，输出你能获得的最大得分，每个测试用例输出一行。

对于第一个测试用例，最优的做法是对两个元素各进行 $5$ 次操作，此时 $a = [8,8]$。所以最大得分为 $\max(8 + \operatorname{median}[8], 8 + \operatorname{median}[8]) = 16$，因为 $c_1 = [a_2] = [8]$。可以证明无法获得更高的得分。 对于第二个测试用例，你无法对任何元素进行操作，所以 $a$ 仍为 $[3,3,3]$。所以最大得分为 $3 + \operatorname{median}[3, 3] = 6$，因为 $c_1 = [a_2, a_3] = [3, 3]$。可以证明无法获得更高的得分。 由 ChatGPT 4.1 翻译