题解 – P3076 [USACO13FEB] Taxi G

题目链接

长度为 m 的栅栏上，有 n 头牛需要坐车前往别的地方，起点和终点分别为 a_i 和b_i 。现在一辆出租车从最左端 0 出发，要运送完所有牛，最后到达最右端m ，求最小路程。出租车只能一次载一只牛。

题解

超级无敌大水题思维题

首先，出租车要将每个牛都从出发点送到目的地，那么必须经过所有牛的路程。我们先将这个路程加上。

然后考虑出租车没有载牛的时间，那么这个时间就是从某个终点到某个起点。同时，假设 0 是上一个终点，m 是下一个终点，就能处理这个最短距离。

最短距离，且都是匹配的 l_i, r_i，证明笔记 – 关于两个序列的顺序对 ∑(a_i−b_i)^2 的影响。我们将两个序列排一下序，最后逐次加上差值即可。

AC Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define abs_sub(x, y) ((x) > (y) ? (x) - (y) : (y) - (x))
const int N = 1e5 + 10;
int n, m;
int l[N], r[N];
ll ans;
int main()
{
  scanf("%d%d", &n, &m);
  for(int i = 1; i <= n; i++) {scanf("%d%d", &l[i], &r[i]);ans += abs_sub(r[i], l[i]);}
  l[++n] = m, r[n] = 0;
  sort(l + 1, l + n + 1); sort(r + 1, r + n + 1);
  for(int i = 1; i <= n; i++) {ans += abs_sub(r[i], l[i]);}
  printf("%lld\n", ans);
  return 0;
}