CVBB ACM Team

本页面只读。您可以查看源文件，但不能更改它。如果您觉得这是系统错误，请联系管理员。

===== 题意简述 =====
有两个长度为 $n$ 的数列 $a$ 和 $b$ ，现在可以在数列 $a$ 中至多进行一次交换操作，问 $d=\sum{|a_i-b_i|}$ 至少为多少。

$ n \le 10^6\ ,|a_i|,|b_i| \le 10^9$

===== 题解 =====
考虑最终求的值为每个区间 $[min(a_i,b_i),max(a_i,b_i)]$ 的长度之和（这里长度定义均为右端点减左端点的值）。交换 $a_i$ 和 $a_j$ 会使答案变小，当且仅当 $a_i$ 和 $b_i$ 的大小关系与 $a_j$ 和 $b_j$ 的大小关系相反，且两个区间有交。这个地方的证明比较简单，可以通过枚举来证明。进一步的，我们可以知道这次交换会使答案变小的值为 $2*交集长度$ 。

考虑怎么求这个值，首先我们将这些区间按照左端点来排序，之后从小到大遍历这些区间，注意到前面的区间左端点均在当前区间左侧，所以交集长度就是两者的右端点取较小值之后作为右端点的区间长度，这里可以分别维护两种大小关系的最靠右的右端点来实现。

总体的时间复杂度瓶颈在于排序，因此复杂度是 $O(n \log{n})$ 的。

CVBB ACM Team

用户工具

站点工具

页面工具