自动搬运

查看原文

来自洛谷，原作者为

	Unordered_OIer **

搬运于2025-08-24 22:35:48，当前版本为作者最后更新于2024-08-30 23:16:31，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

P8083

题意：给定序列 $a,b$，要求选出一个序列 $b$ 的排列 $b'$，满足序列 $a$ 与 $b'$ 的任意相同位置的相邻元素的大小关系相同，并且最大化 $\sum\limits_{i=2}^n|b'_i-b'_{i-1}|$。

容易发现，一个单调的序列的“权值”仅和该序列中最大最小值有关。于是，例如样例中的 9 5 1 2 6 7 4 18 20 12，我们需要关心的“关键位置”只有存在“转折”关系，即同时小于或者大于左右两个相邻位置的位置。在样例中，就是 1、7、4、20 这几个位置，显然答案只和这几个位置的值，以及首位两个位置的值有关。

要求权值最大，不难想到贪心地取 $b$ 中最大的和最小的若干个数填入这些关键位置。具体地，对于满足 $a_{i-1}<a_i$ 且 $a_i>a_{i+1}$ 的位置，我们依次从大到小地用 $b$ 中大的值去填，对于满足 $a_{i-1}>a_i$ 且 $a_i<a_{i+1}$ 的位置，我们依次从小到大地用 $b$ 中小的值去填。

需要注意一些地方就是，我们不能将最小/最大的数填在第一位或最后一位，因为这样会浪费最大最小值做差产生的绝对值（例如样例中 1 4 2 3 打不过 2 4 1 3 就是因为浪费了 $|3-1|$ 和 $|4-1|$）。正确的做法是将 $1$ 和 $n$ 最后填即可，不难发现这样对于权值的损失是最小的。

剩下的非关键位置，我们可以使用剩余的值在每一段中填入，由上述贪心算法填数后剩下的值在 $b$ 数组从小到大排序后一定处于中间一段，所以一定有满足要求的填法。

代码实现很简单，990B/164ms 轻松最优解。