CF1921D Very Different Array 题解

补充一个对本题贪心思路更（？）清楚的解释。

本题贪心思路：

• 在 \(a_i,b_i\) 分别升序的情况下，对于每个 \(a_i\)，与它差值最大的 \(b_i\) 只可能出现在 \(b_{n-i+1}\) 与 \(b_{m-i+1}\) 这两者中。

证明：

首先，假设我们有一个长度为 \(n\) 的升序序列 \(s\)。

则对于 \(s_1\)，与它差值最大的元素为 \(s_n\)；

对于 \(s_2\)，与它差值最大的元素为 \(s_{n-1}\)。

于是综上，我们得到对于 \(s_i\)，与它差值最大的元素为 \(s_{n-i+1}\)。

同理，对于每个 \(a_i\)，与它差值最大的元素一定形如 \(b_{x-i+1}\)。

那么，在所有的形如 \(b_{x-i+1}\) 的元素中，最小的一定是 \(b_{n-i+1}\)，最大的一定是 \(b_{m-i+1}\)。

原因如下：

• 首先，不会有比 \(n-i+1\) 更小的下标，因为 \(i\) 最大为 \(n\)。

• 其次，也不可能存在 \(b_{x-i+1}\) 使得它小于 \(b_{n-i+1}\) 且 \(x>n\)，因为 \(b_i\) 升序。

同理也可得最大的一定是 \(b_{m-i+1}\)。

然后又因为只有最小值和最大值才能成为与 \(a_i\) 差值最大的元素，所以对于每个 \(a_i\)，与它差值最大的 \(b_i\) 只可能出现在 \(b_{n-i+1}\) 与 \(b_{m-i+1}\) 这两者中。

证毕。

代码非常好写，就不贴了。