自动搬运

查看原文

来自洛谷，原作者为

	McIron233 喵喵？

搬运于2025-08-24 22:56:48，当前版本为作者最后更新于2024-02-28 19:48:34，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

数据人题解。

考虑到 $a_i$ 的顺序并不影响答案的相对位置，因此对 $a_i$ 从小到大排序。

从题目的第二个条件入手：

$\dfrac{\sum\limits_{i=1}^n (a_i \cdot b_i)}{\sum\limits_{i=1}^n b_i}$ 为整数，即 $a_i$ 的权为 $b_i$ 时，序列 $a$ 的加权平均数为整数。

设这个加权平均数为 $\lambda$，那么有：

$$\begin{aligned} &\ \frac{\sum\limits_{i=1}^n (a_i \cdot b_i)}{ \sum\limits_{i=1}^n b_i}=\lambda \\ &\ \sum\limits_{i=1}^n (a_i \cdot b_i)=\lambda \sum\limits_{i=1}^n b_i \\ &\ \sum\limits_{i=1}^n (a_i \cdot b_i)=\sum\limits_{i=1}^n (\lambda b_i) \\ &\ \sum\limits_{i=1}^n (a_i \cdot b_i)-\sum\limits_{i=1}^n (\lambda b_i)=0 \\ &\ \sum\limits_{i=1}^n [b_i (a_i - \lambda)]=0 \end{aligned} $$

因此当 $\lambda$ 确定，整个序列 $c_i=a_i - \lambda$ 就确定，相应的 $b_i$ 也就有比较简单的构造方案了，问题转化成找到一个合适的 $\lambda$。显然，当 $\lambda$ 离 $a_i$ 中位数越近，序列 $b_i$ 越好构造。

考虑直接取中位数，那么我们需要根据 $n$ 的奇偶性分类讨论：

$n$ 是奇数

那么直接取 $\lambda = a_{\lceil \frac{n}{2} \rceil}$，然后得到序列 $c_i$。显然，$c_i$ 是单调递增的，且前 $\lfloor \dfrac{n}{2} \rfloor$ 个元素都是负数，后 $\lfloor \dfrac{n}{2} \rfloor$ 个元素都是正数。所以我们可以在 $i \not= \dfrac{n}{2}$ 时直接取 $b_i={| c_{n-i+1} |}$；在 $i = \dfrac{n}{2}$ 时，直接取 $b_i=m$。

证明：第二个条件已由刚才的构造得到满足。

对于第一个条件“序列 $b$ 中的每个元素均为不大于 $m$ 的正整数”，容易发现 $| a_n-\lambda | < m$ 且 $| a_1-\lambda | < m$，那么第一个条件也就能进而成立。

对于第三个条件“不存在有序三元整数组 $(i,j,k)$，满足 $1\le i<j<k\le n$ 且 $b_i=b_j=b_k$”，我们发现由于 $a_i$ 是互不相同的，因此 $c_i$ 中绝对值相等的数也最多只有 $2$ 个，不会达到 $3$ 个，此外，$a_n - \lambda <m$，所以 $c_i$ 中没有绝对值为 $m$ 的元素。故第三个条件同样满足。

举一个构造例子。当 $a_i=\{1,3,4,6,7\}$，$m=7$ 来说，$\lambda=a_3=4$，得到 $c_i=\{-3,-1,0,2,3\}$，对应有：$b_1=|c_{5-1+1}|=|c_5|=3$，其余元素同理，且 $b_3=m=7$，于是 $b_i=\{3,2,7,1,3\}$。

$n$ 是偶数

这时候需要进行简单转化。容易发现当序列 $a_i$ 中间两个数不连续时直接取 $\lambda$ 满足 $a_{\frac{n}{2}}<\lambda<a_{\frac{n}{2}+1}$，然后类比 $n$ 是奇数的方法来构造即可，不同点是不需要确定 $b_\frac{n}{2}$ 的值。

如果中间两个元素连续，考虑取 $\lambda$ 是中间两个元素中的一个，接下来使用如下的构造方法。

构造方法

这里取 $\lambda=a_{\frac{n}{2}}$，那么得到的序列 $c_i$ 中负数元素数量比正数元素数量少 $1$ 个。考虑合并两个正数元素。容易发现此时 $c_{\frac{n}{2}+1}=1$，因此将 $c_{\frac{n}{2}+1}$ 与 $c_n$ 合并，具体方式是：$c_n \leftarrow c_n+1$，然后与 $n$ 是奇数的相似方法（有不同点）构造，再 $b_{\frac{n}{2}+1} \leftarrow b_n$ 就完成了。

显然，在这种情况下 $n=2$ 时是无解的，证明可以从另一个角度——分离常数法来解释。

不同点：由于第三个条件“不存在有序三元整数组 $(i,j,k)$，满足 $1\le i<j<k\le n$ 且 $b_i=b_j=b_k$”，我们为合并后的 $c_n$ 配对时，需要在 $[1,n)$ 中寻找一个合适的 $c_i$ 满足 $c_i \not=c_n$。所以有可能出现找不到这样的 $c_i$ 的情况，那么取 $\lambda=a_{\frac{n}{2}}$ 时就不可行了，换用 $\lambda=a_{\frac{n}{2}+1}$，然后类比该构造方法。可以证明两个 $\lambda$ 中至少有一个是可行的。

关于两个 $\lambda$ 至少一者可行的证明

这里给出两个 $\lambda$ 取值时得到的 $c_i$ 序列：

$\lambda$ 取值/下标	$1$	$2$	$\cdots$	$\dfrac{n}{2}$	$\dfrac{n}{2}+1$	$\cdots$	$n-1$	$n$
$a_{\frac{n}{2}}$	$x_1$	$x_2$	$\cdots$	$0$	$1$	$\cdots$	$x_{n-1}$	$x_n$
$a_{\frac{n}{2}+1}$	$x_1-1$	$x_2-1$		$-1$	$0$		$x_{n-1}-1$	$x_n-1$

注：$x_i$ 互不相同。

根据 $c_i$ 的单调递增性，两个 $\lambda$ 都不合法的必要条件是：

$$\begin{cases} x_1+1+x_n=0 \\ x_1-1-1+x_n-1=0 \end{cases} $$

而这个方程组没有解。所以两个 $\lambda$ 中至少有一者合法。

构造时间复杂度

单组测试数据的时间复杂度是 $O(n \log n)$，瓶颈在排序。