题解：CF2140D A Cruel Segment's Thesis

· · 题解

给出 N 条线段 [l_i,r_i]，求两两匹配，使每一对 (i,j) 的 r_j-l_i 和最大。

一个显然的思路使选 \dfrac n2 个 R 最大的，减掉 \dfrac n2 的 L 最小的。然而可能 L 与 R 同属一条线段。写出答案的贡献式：

\begin{aligned}\sum\limits_{i\in H}r_i-\sum\limits_{i\in L}l_i&=\sum\limits_{i=1}^n r_i-\sum\limits_{i\in L}(l_i+r_i)\end{aligned}

可以发现，我们只需最小化 \sum\limits_{i\in L}(l_i+r_i) 就能最大化答案。

对于奇数的情况，继续写式子：

\begin{aligned}\sum\limits_{i\in H}r_i-\sum\limits_{i\in L}l_i&=\sum\limits_{i=1}^n r_i-\sum\limits_{i\in L}(l_i+r_i)-r_{rest}\end{aligned}

其中 r_{rest} 是剩下未匹配的那个线段的右端点。发现只需要枚举每条线段作为 rest 的情况（若 rest 在算的 L 中，只需向后顺延一位即可，这是 \mathcal O(1) 的），就算完答案了。

Submission