题目大意

有 $n$ 张卡牌，第 $i$ 张正面数字为 $a_i$，背面数字为 $b_i$。初始全部正面朝上，可以翻面最多 $m$ 张牌。目标是让最终朝上的 $n$ 个数字的极差（最大值减最小值）最小。

解题思路

核心思想

贪心 + 双指针 + 预处理优化

1. 翻面策略分析：最优解中，翻面的卡牌应该集中在序列的两端
2. 单调性利用：利用 $a_i$ 已排序的性质，通过预处理快速计算区间最值
3. 双指针扫描：枚举前后翻面数量，动态调整找到最优解

算法流程

1. 预处理阶段

• 前缀最值数组：mxf[i]、mnf[i] 表示前 $i$ 张牌翻面后的最大/最小值
• 后缀最值数组：mxb[i]、mnb[i] 表示后 $i$ 张牌翻面后的最大/最小值

2. 边界确定

• id1：找到第一个 $a[i] > b[i]$ 的位置，之前的位置翻面可能更优
• id2：找到最后一个 $a[i] < b[i]$ 的位置，之后的位置翻面可能更优

3. 双指针扫描

• i：枚举前部翻面数量（0 到 min(m, id1)）
• j：枚举后部翻面数量，动态调整满足约束
• 对于每个 (i, j) 组合，调用 calc 计算极差

4. 极差计算 (calc函数)

考虑三种情况：

1. 前部翻面：使用 b[1..i] 替代 a[1..i]
2. 后部翻面：使用 b[n-j+1..n] 替代 a[n-j+1..n]
3. 中间保留：a[i+1..n-j] 保持不变

取这三部分的最大值和最小值计算极差。

复杂度分析

• 时间复杂度：$O(n)$

  • 预处理：$O(n)$
  • 双指针扫描：$O(n)$，每个位置最多被访问常数次

• 空间复杂度：$O(n)$

总结

本题的巧妙之处在于：

1. 问题简化：通过分析发现最优翻面方案集中在序列两端，将问题转化为前后缀翻面数量的枚举

2. 预处理优化：通过前缀后缀最值数组，快速计算任意翻面方案下的极差

3. 双指针技巧：利用单调性动态调整翻面数量，避免暴力枚举

4. 边界处理：通过 id1 和 id2 进一步缩小搜索范围，提升效率