极差题解

SafariMo · 2024-02-15 18:23:26 · 题解

首先注意到将 a 拆分成 2 个子序列显然比拆分成多于 2 个是要更优的，因为可以把子序列合并成两个。

然后我们发现，序列中的最大值和最小值一定会影响极差。

分类讨论一下：

• 最大值和最小值在同一子序列中，则必须满足另一个子序列也同时包含最大值和最小值，也就是说最大值和最小值出现次数都超过两次。
• 最大值和最小值不在同一子序列中，并假设最大值在第一个子序列中，设第一个子序列的最小值为 p，第二个子序列的最大值为 q。则有 \max- \ p=q-\min，移项后得 \max+\min=p+q，并有构造方式如下：将 \ge q 的数全部放入第一个子序列，\le p 的数放入第二个子序列，剩下的随便放，因此只需确定 p,q 就满足条件。

发现两种情况都可以转换为 \max+\min=p+q，直接用桶实现即可。