← 返回题目列表

Codeforces · 2246/D

D. diss_quack 和数组游戏

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

给定一个由 $$$n$$$ 整数组成的数组 $$$a$$$。 Alice 和 Bob 将用这个数组玩一个游戏。

在与 Bob 的游戏开始之前,Alice 可以任意次数地递增数组中的任何元素,每次递增需要移动一步。一个增量由 $$$1$$$ 向一个索引单次添加组成。

之后,游戏开始,Bob 和 Alice 轮流进行, 鲍勃 迈出了第一步。轮到 Bob 时,他可以选择任意两个索引 $$$i$$$ 和 $$$j$$$ 并交换这些索引处的数组元素(请注意,Bob 可以选择 $$$i = j$$$,在这种情况下,交换后数组保持不变)。

轮到Alice,如果$$$a_1$$$是偶数,她找到最大的$$$j \leq |a|$$$,使得$$$a_i$$$对于所有$$$i \leq j来说都是偶数,$$$然后为$$$i \leq j设置$$$a_i := a_i/2$$$。$$$否则她设置$$$a_1 := a_1 - 1.$$$ 如果任何元素变为零,它会自动从数组中删除(并且其他元素相应地重新索引)。

当数组为空时游戏结束。

Alice 希望最小化她的移动次数,而 Bob 希望最大化 Alice 的移动次数。请注意,移动次数是初始添加次数与爱丽丝随后玩的回合数之和。

Alice 在最佳玩法下会走多少步?

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n \, (1 \le n \le 10^5)$$$ — 数组的长度。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_{n}\,(1 \le a_i \le 10^5)$$$ — 数组的元素。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^5$$$。

输出

对于每个测试用例,输出一个整数 - 如果两个玩家都发挥最佳状态,Alice 将进行的移动次数。

示例

输入
复制

4
3
1 2 3
4
2 2 2 2
5
6 8 2 4 1
8
1 3 5 7 9 11 13 15

输出
复制

6
5
12
35

注意

在第一种情况下,Alice 选择最初不添加任何元素。第一步,Bob 选择 $$$i = j = 1$$$ (不交换任何元素)。然后 Alice 从 $$$a_1,$$$ 中减去 $$$1$$$,得到数组 $$$[2,3]$$$。接下来,Bob 再次选择 $$$i = j = 1。$$$ Alice 将 $$$a_1$$$ 除以 $$$2$$$,数组变为 $$$[1,3]$$$。 Bob 再次选择 $$$i = j = 1。$$$ Alice 从 $$$a_1,$$$ 中减去,数组变为 $$$[3]$$$。鲍勃现在必须选择 $$$i = j = 1,$$$,而爱丽丝则需要采取 $$$3$$$ 操作才能将数组清空。爱丽丝总共走了 $$$6$$$ 步。可以证明这是最优发挥的结果。

在第二个测试用例中,Alice 再次选择最初不添加任何元素。可以证明,在最佳玩法下,爱丽丝采取 $$$5$$$ 步。