P3076 [USACO13FEB] Taxi G 题解

耶梦加得 · 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);
}