P8083

· · 题解

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 轻松最优解。