题目描述

难度分:$1704$

输入$n(2 \leq n \leq 3 \times 10^5)$，然后输入$n$行，每行两个数，表示一个闭区间的左右端点$L[i]$和 $R[i]$，数值范围在$[1,10^7]$内。

你需要从每个闭区间内，各选择一个整数。这$n$个数构成了数组$x$。

设$s$为所有$|x[j] - x[i]|$的和，其中$i \lt j$。

相当于把$x$中的所有数放在一条数轴上，计算所有点对的距离之和。

输出$s$的最小值。

输入样例$1$

3
1 3
2 4
5 6

输出样例$1$

4

输入样例$2$

3
1 1
1 1
1 1

输出样例$2$

0

输入样例$3$

6
1 5
2 4
1 1
4 4
3 6
3 3

输出样例$3$

15

算法

贪心

由于是绝对值，我们将$x$有序与否并不影响目标函数$s=\Sigma_{i=1}^{n-1}\Sigma_{j=i+1}^{n}|x[j]-x[i]|$的值。但是如果$x$有序，就可以去掉绝对值，最终将目标函数化为

$s=(n-1) \times (x[n]-x[1])+(n-3) \times (x[n-1]-x[2])+…=\Sigma_{i=1}^{\frac{n}{2}}(n-2i+1) \times (x[n-i+1]-x[i])$

这是因为$x[n]$要减去$x[n-1]$、$x[n-2]$、……、$x[1]$，$s$中一共有$n-1$个$x[n]$；而$x[n-1]$要减去$x[n-2]$、$x[n-3]$、……、$x[1]$，一共$n-2$个$x[n-1]$，但因为$x[n-1]$要被$x[n]$减一次，所以减少一个$x[n-1]$，$s$中一共有$n-3$个$x[n-1]$。$x[1]$被比它大的$n-1$个数减了，所以一共有$n-1$个$-x[1]$；$x[2]$被比它大的$n-2$个数减了，但由于$x[2]$还会减一次$x[1]$，所以又加回来一个$x[2]$，只有$n-3$个$-x[2]$。此时我们可以将$x[1]$和$x[n]$配对，$x[2]$和$x[n-1]$配对，分别提取公因式$n-1$和$n-3$，接下来依此类推分析$(x[n-2],x[3])$，$(x[n-3],x[4])$,……即可。

因此我们在$x$有序的情况下考虑$s$的最小值，显然$x[1]$和$x[n]$越近肯定$s$就越小，$x[1]$最大可以取到最小的$R$值，否则就没有办法从$R$最小的那个区间里选数；同理，$x[n]$最小可以取到最大的$L$值，否则也没有办法从$L$最大的那个区间里选数。

1. 当$x[1] \lt x[n]$时，可以计算它们对答案的贡献，然后去掉这两个点$n=n-2$，继续考虑规模更小的子问题。
2. 当$x[1] \geq x[n]$时，所有区间存在交集，我们可以在每个区间中选择同一个数，使得它们对答案的贡献为$0$，因此碰到这种情况直接跳过就行了。

实现时可以把左端点和右端点分别排序（左端点降序排列，右端点升序排列，$x[n]$从左端点里面选，$x[1]$从右端点里面选），然后循环扫一遍即可求得答案。每次循环相当于计算$s$中一项的贡献，即每次选$x[n]-x[1]$最小的计算贡献（更新$n=n-2$之后，$x[2]$和$x[n-1]$就变成了新的$x[1]$和$x[n]$）。

复杂度分析

时间复杂度

瓶颈主要在于两次排序，剩下扫描求最终结果的时间复杂度是线性的，因此算法整体的时间复杂度是$O(nlog_2n)$。

空间复杂度

需要存储输入的$(L[i],R[i])$，然后对它们分别排序，因此额外空间复杂度为$O(n)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long LL;

const int N = 300010;
int l[N], r[N], n;

int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {
        scanf("%d%d", &l[i], &r[i]);
    }
    sort(l + 1, l + n + 1);
    reverse(l + 1, l + n + 1);
    sort(r + 1, r + n + 1);
    LL ans = 0;
    for(int i = 1; i <= n && l[i] > r[i]; i++) {
        ans += (LL)(n - 2*i + 1)*(l[i] - r[i]);
    }
    printf("%lld\n", ans);
    return 0;
}