自动搬运

查看原文

来自洛谷，原作者为

	耶梦加得 In the end it doesn't even matter.

搬运于2025-08-24 21:45:03，当前版本为作者最后更新于2022-01-20 15:36:48，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

假如你是一个现实生活中的出租车司机，首先容易想到 $\sum|s_i-t_i|$ 是省不了的起码你得把路程开一遍。

那么除开送乘客的时间，那么剩下的就是要最小化接单时间，也就是从上一个终点到下一个起点的时间。

也许你会想到送完一个乘客去找一个最近的起点。然而连样例都过不去。

分析样例，我们从 $0$ 开到 $6$， 再从 $6$ 开到 $5$， 又从 $5$ 开到 $9$……

显然，为了不空载，我们只会在有牛的地方把乘客扔下去。这一瞬间，这个地点存在两头牛。

这两头牛有区别吗？

没有，众生平等。

这时候这两头牛的命运交汇了，你的起点就是我的起点，于是我们在必要的 $11$ 单位路程之外，只需要 $1$ 单位的拉客路程，那就是从牛 $2$ 的终点到牛 $2$ 的起点（现在已经变成了牛 $1$ 的起点）的路程。

综上所述，我们要把数组 $s,t$ 一一对应，让 $\sum|s_i-t_j|$ 最小。

这里，结论是将 $s,t$ 两数组排序后计算 $\sum_{i=1}^n|s_i-t_i|$

这里的顺序已经和题目中给定的无关了。

无论是小学奥数的小球碰撞，初中化学的复分解反应，还是这道题。

我管你在题目条件里是多么比目鸳鸯双去双来天长地久海枯石烂，都给我拆了！

我只关心我的油费！

至于为什么这个数值最小，可以通过邻项交换证明。 假定 $a_i < a_j , b_i < b_j$。

那么必然有 $|a_i - b_i| + |a_j - b_j| \leq |a_i - b_j| + |a_j - b_i|$。

（这回是真的易证了）

另外需要注意的是，由于你从最左端出发，相当于是刚刚拉着你自己到了 $0$ 处，准备接下一个单子，所以要把 $0$ 算作是一个终点。

同理，最右端是你将要载着自己开始一段新的历程的地方，$m$ 是起点而非终点。

#include<algorithm>
#include<cassert>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<queue>
#include<vector>
#define miu 100007
using namespace std;
inline int abs(register int & x) {
    return x > 0 ? x : -x;
}
int n, m;
int s[miu], t[miu];
long long ans = 0;
signed main() {
    scanf("%d %d", &n, &m);
    t[0] = 0; //看作是刚拉完客等在栅栏左端
    s[0] = m; //最后的乘客是你自己，你将驶出栅栏，迈向天涯
    for(int i = 1; i <= n; ++i) {
        scanf("%d %d", s + i, t + i);
        ans += abs(s[i] - t[i]);
    }
    sort(s, s + n + 1); sort(t, t + n + 1);
    for(int i = 0; i <= n; ++i) {
        ans += abs(s[i] - t[i]);
    }
    printf("%lld\n", ans);
}