自动搬运

查看原文

来自洛谷，原作者为

	yinhy09 既然选择了远方，便只顾风雨兼程~

搬运于2025-08-24 22:43:49，当前版本为作者最后更新于2022-12-15 22:23:47，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

官方题解

本题是求 一个 $a$ 的排列使得 $\left|pa_1-qa_2\right|+\left|pa_2-qa_3\right|+\cdots+\left|pa_{n-1}-qa_n\right|+\left|pa_n-qa_1\right|$ 最大。

将式子拆开：

$(p\times a_1,q\times a_2)$
$(p\times a_2,q\times a_3)$
$(p\times a_3,q\times a_4)$
$\vdots$
$(p\times a_{n-2},q\times a_{n-1})$
$(p\times a_{n-1},q\times a_{n})$
$(p\times a_{n},q\times a_{1})$

（下简记第 $i$ 个括号对内第 $j$ 个数为 $x_{i,j}$。）

上面的 $2n$ 个数，当我们把绝对值按照实际情况拆开以后，会有 $n$ 项前面系数为 $+1$，$n$ 项前面的系数为 $-1$。由于我们希望原式尽可能大，所以希望大的 $n$ 个都是正，小的是负；这样取到一个理论最大值。（不希望大的和大的放在同一行，这样相减会降低大数的价值）

但是自然会有一个问题，这个理论最大值是否能取到？

我们构造两个集合 $A,B$，记录上面 $2n$ 个数中较大的一半和较小的一半。

显然，只要 $x_{i,2}$ 的分解（此处不说数是因为 $2\times 6$ 和 $3\times 4$ 结果一样，但是分解方式不一样）确定，$x_{i+1,1}$ 的分解也就确定了。我们假设从 $x_{1,2}$ 开始填，先随机选一个分解填入（不管在 $A,B$ 哪个集合当中），那么 $x_{2,1}$ 就确定了。如果 $x_{2,1}$ 是在 $A$ 集合中的分解，那么我们就从 $B$ 中随便找一个填到 $x_{2,2}$。

如此反复，直到表格被填满，因为我们是从 $A,B$ 集合中交替取数，所以不可能有某时刻需要某个集合的数但是没有的情况。

故理论最大值可以被取到。

构造方法只需找一个地方开始填表即可。