D. A Cruel Segment's Thesis

问题

在数轴上给定 $n$ 个线段。第 $i$ 个线段表示为 $[l_i,r_i]$。最初，所有线段都未被标记。

你重复执行以下操作，直到没有未标记的线段为止：

在第 $k$ 次操作中，如果至少有两个未标记的线段，选择任意两个未标记的线段 $[l_i,r_i]$ 和 $[l_j,r_j]$，将它们都标记，并添加一个满足以下条件的新的标记线段 $[x_k,y_k]$： $l_i \leq x_k \leq r_i$， $l_j \leq y_k \leq r_j$， $x_k \leq y_k$。 如果只剩下一个未标记的线段，则将其标记。 你的任务是确定在过程结束时，所有标记线段的长度之和的最大可能值。注意，线段 $[l,r]$ 的长度为 $r-l$。

题解与观察

解法可以根据线段数量是奇数还是偶数分为两种情况。

情况1：偶数个线段

当 $n$ 是偶数时，我们可以将所有线段最优地配对。对于每一对：

• 一个线段将提供右端点 ($r_i$)
• 一个线段将提供左端点 ($l_i$)

总和可以表示为：

为了进一步优化，我们可以将其转换为：

这个转换揭示了，为了最大化总和，我们需要：

1. 最初包含所有右端点
2. 移除 $(l_i + r_i)$ 的最小的 $n/2$ 个值

情况2：奇数个线段

当 $n$ 是奇数时，会有一个线段未配对。策略是：

1. 将每个线段都视为可能未配对的那个
2. 对于剩余的偶数个线段，应用与情况1中相同的优化
3. 选择产生最大总和的配置

查看题解