手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

每日速看!C. Sequence Master

2023-03-19 18:01:50 来源：博客园

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

416 921 2 2 12-2 -2 2 24-3 -2 -1 0 1 2 3 4

output

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  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  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

关键词：