P3076 [USACO13FEB] Taxi G
Description
有一条长度为 \(m\) 的数轴，有 \(n\) 头牛需要坐车前往别的地方，起点和终点分别为 \(a_i\) 和 \(b_i\)。
现在一辆出租车从原点出发，要运送完所有牛，最后到达最右端 \(m\)，求最小路程。出租车只能一次载一只牛。
Solution
我们先来看一下样例。
2 10
0 9
6 5
不难发现其中有 \(a_i>b_i\) 的情况。而且题中指出一次只能载一头牛，所以会出现以下的情形：
你把第一头牛从 0 送到 6，然后把他扔了，再把第二头牛从 6 送回到 5。
你从 5 空载走到 6 ，最后把第一头牛从 6 送到 9，再走到终点 \(m\)。
我们观察一下这个式子的构成（我们不妨认为自己是一头奶牛，要把自己从起点 0 送到终点 \(m\)）。
由于每头牛至少要从自己的起点走到终点，所以答案中必然包含 \(\sum_{i=1}^{n} |a_i-b_i|\)。
看上面这个图能帮助理解。不难发现每个红线都是从 \(a_i\) 到 \(b_j\)，所以最终答案就是
\[\sum_{i=1}^{n}|a_i-b_i|+\sum |a_i-b_j|
\]
现在我们的任务变成了最小化 \(\sum |a_i-b_j|\)。考虑对 \(a\) 和 \(b\) 排序即可。
#include<bits/stdc++.h>
using namespace std;
long long n,m,a[100010],b[100010],ans;
signed main(){cin>>n>>m;for(int i=1;i<=n;i++){cin>>a[i]>>b[i];ans+=abs(a[i]-b[i]);}a[n+1]=m;b[n+1]=0;sort(a+1,a+n+2);sort(b+1,b+n+2);for(int i=1;i<=n+1;i++){ans+=abs(a[i]-b[i]); }cout<<ans<<endl;return 0;
}
最后是证明。
假设当前的方案不是最优，那么一定存在至少一对 \(i,j\)，使得接第 \(j\) 头牛比接第 \(i\) 头牛更优。那我们不妨计算交换 \(i\) 和 \(j\) 所产生的影响。
经过排序后，\(a_i<a_{j}\)，且 \(b_i<b_{j}\)。交换前对答案的贡献为 \(|a_i-b_i|+|a_j-b_j|\)。
交换后，贡献为 \(|a_{i}-b_j|+|b_i-a_j|\)，显然不优。