GMOI R1 T4 Solution

· · 题解

官方题解

本题是求 一个 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 集合中交替取数，所以不可能有某时刻需要某个集合的数但是没有的情况。

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

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