Weighted Mean

· · 题解

数据人题解。

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

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

设这个加权平均数为 \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 \cdots -1 0 \cdots 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)，瓶颈在排序。