自动搬运

查看原文

来自洛谷，原作者为

	bzy 魔法みたいな算法で☆世界を変えるよ

搬运于2025-08-24 22:30:40，当前版本为作者最后更新于2021-04-14 13:44:34，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

Tips : 本解法不一定是正解。

考虑暴力，枚举 $a_k$, 将 $\{a_n\}$ 中除了 $a_k$ 的数字对 $a_k$ 取模，生成新序列 $\{b_n\}$。将 $\{b_n\}$ 中的数字分成两部分 $A, B$。$A$ 中元素小于 $\lceil\frac{n}{2}\rceil$, $B$ 中元素大于等于 $\lceil\frac{n}{2}\rceil$。然后考虑模 $a_k$ 意义下，最大值三种可能的情况:

1. $A$ 中最大值与次大值的和。
2. $B$ 中最大值与次大值的和减去 $a_k$。
3. 枚举 $b_i$ 找到 $\{b_n\}$ 小于 $a_k-b_i$ 的最大值 $b_x$，$b_i+b_x$ 可能为最大值。

视实现情况，复杂度为 $\Theta(n^2\log n)$ ~ $\Theta(n^3)$。

考虑对上述暴力进行优化。

优化一

相同出现过的数字只枚举一次。

看起来用处不大，复杂度依然不变。

优化二

从大到小枚举 $a_k$, 然后记录一个答案 $p$。一旦 $a_k \le p$ 则不再枚举。

看起来用处不大，但结合优化一以后，复杂度下降到 $\mathcal{O}(n\log n\log V)$。其中 $V$ 是 $\{a_n\}$ 的值域大小。

这里的复杂度是一个比较松的上界，应该能找到更紧的界。

以下是这个上界的证明。

证明

考虑弱化上述的优化，即把记录的答案 $p$ 改成暴力中情况 1、2 的最大值，记作 $p=\max\{p_1,p_2\}$。

首先枚举 $\{a_n\}$ 中最大值为 $a_k$，记作 $a_x$。

延续暴力算法中的定义，有 $A$ 中所有元素均小于等于 $p_1$, 所以小于等于 $p$。即 $A$ 中元素无需枚举。所以只考虑 $B$ 中元素。

设 $\lceil\frac{a_x}{2}\rceil\le B_1\le B_2\le \cdots\le B_t\le a_x$。

假设枚举若干轮后 $p$ 变为 $p'$。则我们需要枚举的元素为

$p'\le B_s\le B_{s+1}\le \cdots\le B_t\le a_x$。

将上述不等式逐项相减得到 $\{u_1,u_2,\cdots,u_{t-s+1}\}$。

因为第二类最大值为 $B_i+B_{i+1}-B_{i+2}\le p'$。

所以 $u_i+2u_{i+1}\ge\sum\limits_{j=1}^{i+1}u_j$

要让 $u$ 尽可能小，上述不等式得取等号。

即 $u_{i+1}=\sum\limits_{j=1}^{i-1}u_j$。

此时可知 $u_{i+1}=u_i+u_{i-1}$ 形似斐波那契数列，所以 $u_n=\mathcal{O}((\frac{\sqrt{5}+1}{2})^n)$。

又因为 $B_t-p'=\sum\limits_{i=1}^{t-s+1} u = u_{t-s+2}\le\frac{V}{2}$。

所以需要枚举的数是 $\mathcal{O}(\log V)$ 级的。

总时间复杂度为 $\mathcal{O}(n\log n \log V)$。