← 返回题目列表

Codeforces · 1806/C

C. 序列主控

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

对于某些正整数 $$$m$$$,YunQian 认为 $$$2m$$$(可能是负)整数的数组 $$$q$$$ 是好的,当且仅当对于 $$$q$$$ 的每个可能的长度为 $$$m$$$ 的子序列,子序列中 $$$m$$$ 元素的乘积等于$$$m$$$ 不在子序列中的元素。形式上,令 $$$U=\{1,2,\ldots,2m\}$$$。对于所有集合$$$S \subseteq U$$$,使得$$$|S|=m$$$,$$$\prod\limits_{i \in S} q_i = \sum\limits_{i \in U \setminus S} q_i$$$。

将长度为 $$$k$$$ 的两个数组 $$$a$$$ 和 $$$b$$$ 之间的距离定义为 $$$\sum\limits_{i=1}^k|a_i-b_i|$$$。

给定一个正整数 $$$n$$$ 和一个由 $$$2n$$$ 整数组成的数组 $$$p$$$。

在所有长度为 $$$2n$$$ 的好数组 $$$q$$$ 上查找 $$$p$$$ 和 $$$q$$$ 之间的最小距离。对于所有正整数 $$$n$$$ 都可以显示,至少存在一个好的数组。请注意,您不需要构造达到此最小距离的数组 $$$q$$$。

输入

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

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1\le n\le 2\cdot10^5$$$)。

每个测试用例的第二行包含 $$$2n$$$ 整数 $$$p_1, p_2, \ldots, p_{2n}$$$ ($$$|p_i| \le 10^9$$$)。

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

输出

对于每个测试用例,输出 $$$p$$$ 和好的 $$$q$$$ 之间的最小距离。

示例

输入 #1

4
1
6 9
2
1 2 2 1
2
-2 -2 2 2
4
-3 -2 -1 0 1 2 3 4

输出 #1

3
2
5
13

注意

在第一个测试用例中,最好让 $$$q=[6,6]$$$。

在第二个测试用例中,最好让 $$$q=[2,2,2,2]$$$。