题解 AT_arc201_d Match, Mod, Minimize

Z3k7223 · 2025-06-24 19:01:41 · 题解

更好的阅读体验

Solution

为了方便叙述，下文的下标从 0 开始。

令 a 降序排列，b 升序排列。在 a 上选取一个分界点，使得分界点前面的 a_i+b_i\ge m，这时候前面的 a_i 的贡献就变成了 a_i-m。

再考虑 b_i 的配对，感性理解，越大的 a_i 应该和越小的 b_i 配对，于是实际配对就是从分界点 k 开始配对，形式化的就是将 b_i 与 a_{(i+k)\bmod m} 配对，也就是官方题解里提到的循环移位。

将 b 完成循环移位后，此时显然应有 \forall i, a_i+b_i\ge 0。此外，手搓一下不难发现，分界点越靠前，\max\set{a_i+b_i} 就越大，所以我们只需要二分找到最后的合法分界点并计算贡献即可。

时间复杂度 O(n\log n)。

Code

代码实现将二分的 check 和贡献计算合一起了。

Link.