C. Sequence Master
For some positive integer $m$, YunQian considers an array $q$ of $2m$ (possibly negative) integers good, if and only if for every possible subsequence of $q$ that has length $m$, the product of the $m$ elements in the subsequence is equal to the sum of the $m$ elements that are not in the subsequence. Formally, let $U=\{1,2,\ldots,2m\}$. For all sets $S \subseteq U$ such that $|S|=m$, $\prod\limits_{i \in S} q_i = \sum\limits_{i \in U \setminus S} q_i$.
Define the distance between two arrays $a$ and $b$ both of length $k$ to be $\sum\limits_{i=1}^k|a_i-b_i|$.
You are given a positive integer $n$ and an array $p$ of $2n$ integers.
Find the minimum distance between $p$ and $q$ over all good arrays $q$ of length $2n$. It can be shown for all positive integers $n$, at least one good array exists. Note that you are not required to construct the array $q$ that achieves this minimum distance.
Input
The first line contains a single integer $t$ ($1\le t\le 10^4$) — the number of test cases. The description of test cases follows.
The first line of each test case contains a single integer $n$ ($1\le n\le 2\cdot10^5$).
The second line of each test case contains $2n$ integers $p_1, p_2, \ldots, p_{2n}$ ($|p_i| \le 10^9$).
It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot 10^5$.
Output
For each test case, output the minimum distance between $p$ and a good $q$.
Example
input
4 1 6 9 2 1 2 2 1 2 -2 -2 2 2 4 -3 -2 -1 0 1 2 3 4
output
3 2 5 13
Note
In the first test case, it is optimal to let $q=[6,6]$.
In the second test case, it is optimal to let $q=[2,2,2,2]$.
解题思路
首先直觉上就会觉得满足条件的$q$数量会很少，同时可以发现$q = [ \ \overbrace{0,0,\ldots,0}^{2n} \ ]$一定是满足条件的，因此对于$\forall n \in \mathbb{Z}$，总是存在一个$q$，即一定有解。我们接下来再考虑是否存在其他满足条件的$q$。
先考虑$q$中所有元素都相同的情况。
很明显当$n=1$的情况，必然会有$q_1 = q_2$，可以等于任意值。
当$n=2$，假设每个元素都为$x$，那么必然会有$x^n = n \cdot x \ \Rightarrow \ x = \sqrt[n-1]{n} = 2$。同时根据该等式，很明显当$n > 2$时等式不存在正整数解。
因此只有当$n=1$或$n=2$，才存在除了全$0$以外所有元素都相同的$q$。
接下来考虑$q$中所有元素不都相同的情况，先考虑$n$为偶数的情况。
由于此时$q$中至少存在两个元素不同，不妨假设$q_1 \ne q2$。满足等式$$\begin{cases} q_1\cdot q_3q_4\cdots q_{n+1}=q_2+q_{n+2}+q_{n+3}+\cdots+q_{2n} \ \ \ \ \ \ \ (1) \\\\ q_2\cdot q_3q_4\cdots q_{n+1}=q_1+q_{n+2}+q_{n+3}+\cdots+q_{2n} \ \ \ \ \ \ \ (2) \end{cases}$$
$(1)-(2)$得到$$(q_1-q_2)q_3q_4\cdots q_{n+1}=q_2-q_1 \ \Rightarrow \ (q_1-q_2)(q_3q_4\cdots q_{n+1}+1)=0$$
由于$q_1 \ne q_2$，因此必然有$q_3q_4\cdots q_{n+1}+1 = 0$，即$q_3q_4\cdots q_{n+1} = -1$。由于$q_i \in \mathbb{Z}$，有奇数个$q_i$连乘，故只能有$q_i = -1$。
同理我们考虑其他类似的约束条件，即$U=\{3, 4, \ldots, 2n\}$，对于$U$所有满足$|S| = n-1$的子集$S \subseteq U$，有$$\begin{cases} q_1 \cdot \prod\limits_{i \in S} q_i = q_1 + \sum\limits_{i \in U \setminus S} q_i \\\\ q_2 \cdot \prod\limits_{i \in S} q_i = q_2 + \sum\limits_{i \in U \setminus S} q_i \end{cases}$$
就可以发现$q_3=q_4=\cdots =q_{2n} = -1$，把结果代入$(1)$式，就会得到$q_1+q_2=n-1$。同时又因为$q_1q_2\cdots q_n=q_{n+1}+\cdots q_{2n}$，因此有$q_1q_2=-n$。这样就可以解得$\{q_1,q_2\}=\{-1,n\}$。
即对于$n$为偶数的情况，我们可以构造出$q = [ \ \overbrace{-1,-1,\ldots,-1}^{2n-1}, \ n \ ]$。
那么对于$n$为奇数的情况呢？与上面的推导过程一样，最后得到$q_3q_4\cdots q_{n+1} = -1$，由于$q_i \in \mathbb{Z}$，此时有偶数个$q_i$连乘，很明显此时没有解。
故只有当$2 \mid n$，有$q = [ \ \overbrace{-1,-1,\ldots,-1}^{2n-1}, \ n \ ]$。
接下来我们只需要针对$n$来分类讨论取最小值就可以了：
- 先考虑$q$中元素均为$0$的情况，此时最小值为$\text{ans} = \sum\limits_{i=1}^{2n}{|p_i|}$。
- 如果$n=1$，为了得到最小值构造$q = [p_1, p_1]$或$q = [p_2, p_2]$，那么就有$\text{ans} = \min\left\{ \text{ans}, \ |p_1 - p_2| \right\}$。
- 如果$n=2$，构造$q = [2,2,2,2]$，那么就有$\text{ans} = \min\left\{ \text{ans}, \ \sum\limits_{i=1}^{4}{|p_i - 2|} \right\}$。
- 最后如果$2 \mid n$，构造$q = [ \ \overbrace{-1,-1,\ldots,-1}^{2n-1}, \ n \ ]$。对$p$从小到大排序，那么就有$\text{ans} = \min\left\{ \text{ans}, \ \sum\limits_{i=1}^{2n}{|p_i - q_i|} \right\}$。
关于上面的第$4$步，如果有序列$p$和$q$，定义两个序列的距离为$\sum\limits_{i=1}^{n}{|p_i-q_i|}$。如果可以任意排列两个序列的元素，那么当$p$和$q$均满足非递减顺序时，即$p_1 \leq p_2 \leq \cdots \leq p_n$，$q_1 \leq q_2 \leq \cdots \leq q_n$，此时距离能够取到最小值，证明见附录部分。
AC代码如下，时间复杂度为$O(n \log{n})$：
1 #include <bits/stdc++.h>
2 using namespace std;
3
4 typedef long long LL;
5
6 const int N = 4e5 + 10;
7
8 int a[N];
9
10 void solve() {
11 int n;
12 scanf("%d", &n);
13 n *= 2;
14 LL ret = 0;
15 for (int i = 0; i < n; i++) {
16 scanf("%d", a + i);
17 ret += abs(a[i]);
18 }
19 if (n == 2) {
20 ret = min(ret, (LL)abs(a[0] - a[1]));
21 }
22 else if (n == 4) {
23 LL s = 0;
24 for (int i = 0; i < n; i++) {
25 s += abs(a[i] - 2);
26 }
27 ret = min(ret, s);
28 }
29 if (n / 2 % 2 == 0) {
30 sort(a, a + n);
31 LL s = abs(a[n - 1] - n / 2);
32 for (int i = 0; i < n - 1; i++) {
33 s += abs(a[i] + 1);
34 }
35 ret = min(ret, s);
36 }
37 printf("%lld\n", ret);
38 }
39
40 int main() {
41 int t;
42 scanf("%d", &t);
43 while (t--) {
44 solve();
45 }
46
47 return 0;
48 }
其中对于第$4$步，由于$q$中只有一个元素是$n$，其余的元素都是$-1$，因此我们可以枚举$p$中哪个元素与$n$求差。定义$s = \sum\limits_{i=1}^{2n}{|p_i+1|}$，那么如果$p_k$与$n$作差，就有$\sum\limits_{i=1}^{n}{|p_i-q_i|} = s - |p_k+1| + |p_k-n|$。
AC代码如下，时间复杂度为$O(n)$：
1 #include <bits/stdc++.h>
2 using namespace std;
3
4 typedef long long LL;
5
6 const int N = 4e5 + 10;
7
8 int a[N];
9
10 void solve() {
11 int n;
12 scanf("%d", &n);
13 n *= 2;
14 LL ret = 0;
15 for (int i = 0; i < n; i++) {
16 scanf("%d", a + i);
17 ret += abs(a[i]);
18 }
19 if (n == 2) {
20 ret = min(ret, (LL)abs(a[0] - a[1]));
21 }
22 else if (n == 4) {
23 LL s = 0;
24 for (int i = 0; i < n; i++) {
25 s += abs(a[i] - 2);
26 }
27 ret = min(ret, s);
28 }
29 if (n / 2 % 2 == 0) {
30 LL s = 0;
31 for (int i = 0; i < n; i++) {
32 s += abs(a[i] + 1);
33 }
34 for (int i = 0; i < n; i++) {
35 ret =min(ret, s - abs(a[i] + 1) + abs(a[i] - n / 2));
36 }
37 }
38 printf("%lld\n", ret);
39 }
40
41 int main() {
42 int t;
43 scanf("%d", &t);
44 while (t--) {
45 solve();
46 }
47
48 return 0;
49 }
附录
有序列$p$和$q$，定义两个序列的距离为$\sum\limits_{i=1}^{n}{|p_i-q_i|}$，序中的元素可以任意重新排序。证明当满足$p_1 \leq p_2 \leq \cdots \leq p_n$，$q_1 \leq q_2 \leq \cdots \leq q_n$时，两个序列的距离取到最小值。
不妨固定$p$，使得$p_1 \leq p_2 \leq \cdots \leq p_n$。同时$q$不满足$q_1 \leq q_2 \leq \cdots \leq q_n$，因此至少存在一对$q_i$和$q_j$，满足$q_i \geq q_j$且$i < j$。
如果$q_i = q_j$，仅考虑$i, \ j$两个位置对距离的贡献，那么很明显不管是否交换$p_i$和$p_j$，$i, \ j$两个位置对距离的贡献都相同，因此我们只考虑$q_i > q_j$，且$p_i < p_j$的情况。
接下来证明通过交换$q_i$和$q_j$，能够使得$i, \ j$两个位置对距离的贡献减少。为此我们假设$p_i = a, \ p_j = b, \ q_i = d, \ q_j = c$，同时有$a < b, \ c < d$。
分情况讨论：
$1.$ $b \leq c$，即$a < b \leq c < d$：
交换$c$和$d$前，距离为$|a - d| + |b - c| = d - a + c - b$，交换$c$和$d$后，有$d < c$，距离就变成了$|a - c| + |b - d| = c - a + d - b$。交换前减去交换后得到$d - a + c - b - (c - a + d - b) = 0$，即交换后的距离不变。
$2.$ $a \leq c < b$：
$2.1.$ $b \leq d$，即$a \leq c < b \leq d$：
交换$c$和$d$前，距离为$|a - d| + |b - c| = d - a + b - c$，交换$c$和$d$后，有$d < c$，距离就变成了$|a - c| + |b - d| = c - a + d - b$，用交换前的距离减去交换后的距离，得到$d - a + b - c - (c - a + d - b) = 2(b - c) > 0$，即交换后的距离变小。
$2.2.$ $b > d$，即$a \leq c < d < b$：
交换$c$和$d$前，距离为$|a - d| + |b - c| = d - a + b - c$，交换$c$和$d$后，有$d < c$，距离就变成了$|a - c| + |b - d| = c - a + b - d$，用交换前的距离减去交换后的距离，得到$d - a + b - c - (c - a + b - d) = 2(d - c) > 0$，即交换后的距离变小。
$3.$ $c < a$：
$3.1.$ $b \leq d$，即$c < a < b \leq d$：
交换$c$和$d$前，距离为$|a - d| + |b - c| = d - a + b - c$，交换$c$和$d$后，有$d < c$，距离就变成了$|a - c| + |b - d| = a - c + d - b$，用交换前的距离减去交换后的距离，得到$d - a + b - c - (a - c + d - b) = 2(b - a) > 0$，即交换后的距离变小。
$3.2.$ $a \leq d < b$，即$c < a \leq d < b$：
交换$c$和$d$前，距离为$|a - d| + |b - c| = d - a + b - c$，交换$c$和$d$后，有$d < c$，距离就变成了$|a - c| + |b - d| = a - c + b - d$，用交换前的距离减去交换后的距离，得到$d - a + b - c - (a - c + b - d) = 2(d - a) \geq 0$，即交换后的距离变小。
$3.2.$ $d < a$，即$c < d < a < b$：
交换$c$和$d$前，距离为$|a - d| + |b - c| = a - d + b - c$，交换$c$和$d$后，有$d < c$，距离就变成了$|a - c| + |b - d| = a - c + b - d$，用交换前的距离减去交换后的距离，得到$a - d + b - c - (a - c + b - d) = 0，即交换后的距离不变。
综上所述，如果序列$p$满足$p_1 \leq p_2 \leq \cdots \leq p_n$，对于序列$q$如果存在$q_i$和$q_j$满足$q_i > q_j$且$i < j$，那么交换$q_i$和$q_j$能使得距离变小。为了使得距离最小，最终$q$一定满足$q_1 \leq q_2 \leq \cdots \leq q_n$。
定理得证。
同时可以推导得到当序列$p$和$q$满足$p_1 \leq p_2 \leq \cdots \leq p_n$，$q_1 \geq q_2 \geq \cdots \geq q_n$时，两个序列的距离取到最大值。
参考资料
Codeforces Round #858 (Div. 2) Editorial：https://codeforces.com/blog/entry/114048
标签：Sequence,int,交换,距离,leq,cdots,Master,ret From： https://www.cnblogs.com/onlyblues/p/17233791.html