← 返回题目列表

Codeforces · 1998/C

C. 执行操作以最大化分数

中文机器翻译题面 查看原题

给定一个长度为 $$$n$$$ 的数组 $$$a$$$ 和一个整数 $$$k$$$。您还将获得一个长度为 $$$n$$$ 的二进制数组 $$$b$$$。

您最多可以执行以下操作 $$$k$$$ 次:

- 选择索引 $$$i$$$ ($$$1 \leq i \leq n$$$) 使得 $$$b_i = 1$$$。设置 $$$a_i = a_i + 1$$$ (即将 $$$a_i$$$ 增加 $$$1$$$)。

你的分数定义为 $$$\max\limits_{i = 1}^{n} \left( a_i + \operatorname{median}(c_i) \right)$$$,其中 $$$c_i$$$ 表示从 $$$a$$$ 中删除 $$$a_i$$$ 得到的长度为 $$$n-1$$$ 的数组。换句话说,您的分数是从 $$$1$$$ 到 $$$n$$$ 的所有 $$$i$$$ 中 $$$a_i + \operatorname{median}(c_i)$$$ 的最大值。

找出如果您以最佳方式执行操作,您可以获得的最高分数。

对于任意数组 $$$p$$$,$$$\operatorname{median}(p)$$$ 被定义为 $$$\left\lfloor \frac{|p|+1}{2} \right\rfloor$$$ - $$$p$$$ 的第一个最小元素。例如,$$$\operatorname{median} \left( [3,2,1,3] \right) = 2$$$ 和 $$$\operatorname{median} \left( [6,2,4,5,1] \right) = 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$$$。

输出

对于每个测试用例,在新行中输出可以获得的最大值。

示例

输入 #1

8
2 10
3 3
1 1
3 10
3 3 3
0 0 0
4 4
2 1 5 1
0 1 0 1
5 4
7 5 2 5 4
0 0 1 0 1
5 1
5 15 15 2 11
1 0 0 1 1
5 2
10 11 4 10 15
1 1 0 1 0
4 4
1 1 2 5
1 1 0 0
2 1000000000
1000000000 1000000000
1 1

输出 #1

16
6
8
13
21
26
8
3000000000

注意

对于第一个测试用例,最好对两个元素执行 $$$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]$$$。可以证明你不可能得到更好的分数。