Codeforces 2077A 題解

本文簡述 Codeforces 2077A 的題解，題目見連結。

1　題目

1.1　敘述

給定正整數 $n \leq 2 \cdot 10^5$ 與一整數序列 $b = (b_1 \cm b_2, \ldots \cm b_{2n}) \comma$其中 $b_1 \cm b_2, \ldots \cm b_{2n}$ 兩兩相異，且對每個 $i \in \{1 \cm 2, \ldots \cm 2n\}$ 均有 $1 \leq b_i \leq 10^9 \period$

我們需要找到一整數序列 $a = (a_1 \cm a_2, \ldots \cm a_{2n+1}) \comma$其滿足以下條件：

1. 存在 $k \in \{1 \cm 2, \ldots \cm 2n \varplus 1\}$ 使得 $(a_1 \cm a_2, \ldots \cm a_{2n} \cm a_{2n+1})$ 為 $(b_1 \cm b_2, \ldots \cm b_{2n} \cm a_k)$ 的一個重排。
2. $\sum_{i=1}^{2n+1} (-1)^{i+1}a_i = 0 \period$
3. $a_1 \cm a_2, \ldots \cm a_{2n+1}$ 兩兩相異。
4. 對每個 $i \in \{1 \cm 2, \ldots \cm 2n \varplus 1\}$ 均有 $1 \leq a_i \leq 10^{18} \period$

1.2　例子

範例 1　假設 $n = 1$ 且 $b = (1 \cm 2) \period$此時可以構造 $a = (1 \cm 3 \cm 2) \period$

範例 2　假設 $n = 2$ 且 $b = (1 \cm 2 \cm 3 \cm 4) \period$此時可以構造 $a = (2 \cm 1 \cm 3 \cm 8 \cm 4) \period$

2　想法

由於重排 $b$ 不會影響題目要求的條件，不失一般性我們假設 $b$ 已經由小到大排序，即 $b_1 < b_2 < \cdots < b_{2n} \period$

我們開始構造 $a \period$我們將 $b$ 中較大的 $n+1$ 項 $b_n \cm b_{n+1}, \ldots \cm b_{2n}$ 依序放在 $a_1 \cm a_3, \ldots \cm a_{2n+1} \comma$並將 $b$ 中較小的 $n-1$ 項 $b_1 \cm b_2, \ldots \cm b_{n-1}$ 依序放在 $a_2 \cm a_4, \ldots \cm a_{2n-2} \period$這樣條件 (1) 即可被滿足，接下來我們只要設定 $a_{2n}$ 的值即可。

為了滿足條件 (2)，我們必須設 \[\begin{split}a_{2n} = \sum_{i=1}^{n+1} a_{2i-1} - \sum_{i=1}^{n-1} a_{2i} = \sum_{i=n}^{2n} b_i - \sum_{i=1}^{n-1} b_i \period\end{split}\]

接著我們檢查在這樣的設定下，條件 (3)、(4) 成立：由 \[\begin{split} a_{2n} &= \sum_{i=n}^{2n} b_i - \sum_{i=1}^{n-1} b_i \\ &= b_{2n} + b_{2n-1} + \sum_{i=n}^{2n-2} b_i - \sum_{i=1}^{n-1} b_i \\ &= b_{2n} + b_{2n-1} + \sum_{i=1}^{n-1} (b_{i+n-1} - b_i) \\ &\geq b_{2n} + b_{2n-1} \end{split}\] 可知 $a_{2n} \geq 1$ 且 $a_{2n} \notin \{b_1 \cm b_2, \ldots \cm b_{2n}\} \period$此外，我們有 \[\begin{split} a_{2n} \leq \sum_{i=n}^{2n} b_i \leq (n+1) \cdot 10^9 \leq 10^{15} \period \end{split}\]

因此以上構造的 $a$ 符合題目的要求。

3　程式碼

以下是 Python 的實作，時間複雜度為 $O(n \lg n) \period$

t = int(input())
for __ in range(t):
    n = int(input())
    b = sorted(map(int, input().split()))
    a = [0 for __ in range(n * 2 + 1)]
    for i in range(n * 2):
        if i < n - 1:
            a[i * 2 + 1] = b[i]
            a[n * 2 - 1] -= b[i]
        else:
            a[(i - n + 1) * 2] = b[i]
            a[n * 2 - 1] += b[i]
    print(*a)