[ARC147C] Min Diff Sum 题解

Getaway_Car · 2025-05-26 19:27:19 · 题解

本文提供一种另类做法。虽然我的代码从实现以及常数上都更劣一些。

考虑原式的几何意义，即在数轴上的 n 个区间内各选一个点使得这 n 个点两两距离之和最小。

考虑什么时候距离之和最小，显然是所有点都尽量向某一个位置靠拢时。所以钦定中心点，让其它所有点都尽量向这个点靠拢，再暴力计算贡献。时间复杂度 O(n^2V)。

注意到，中心点取在非端点显然时不会更优，所以可以离散化。时间复杂度 O(n^3) 。

现在考虑优化计算原式的过程。考虑拆贡献。n 个点把数轴分成 n - 1 条线段（以及两条射线）,那么第 i 条线段就会被计算 i \cdot (n - i) 次。这是显然的。那么我们可以现将这 n 个点排序，再按上述过程计算。时间复杂度 O(n^2 \log n)。

容易发现，在中心点移动的过程中，有许多点的位置并不会随着中心点位置的改变而改变，所以考虑动态维护每个点的位置以及贡献。设当前中心点位置为 pos，可以把 n 个点分成 3 段：

那么我们可以动态维护这三段的端点。当 pos 遇到了一个左端点时，相当于将一个点从第三段移到第二段；当 pos 遇到了一个右端点时，相当于把一个点从第二段移到了第一段。

在此同时，动态维护每段内部的贡献。第一三段的贡献只需要在遇到端点时更新，第二段内部显然没有贡献。总贡献 = 第一段的贡献 + 一二段交界处贡献 + 二三段交界处贡献 + 第三段的贡献。

于是这道题就做完了。

提交记录。