【JZOJ3187】的士【模拟】

本文主要是介绍【JZOJ3187】的士【模拟】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目大意：

题目链接：https://jzoj.net/senior/#main/show/3187
Bessie为农场上的其他奶牛提供的士服务。奶牛们在一条长为$M$的栅栏的不同位置上。不幸的是，它们厌倦了它们现在所在的位置而想要去栅栏上其他的位置。Bessie必须把她每一个朋友从它们各自的起始地接上车然后送它们到目的地。但Bessie的车太小了，所以她每次只能运送一只奶牛。奶牛们上车下车是瞬间的事情。
为了省油钱，Bessie想要使她的驾驶量最小。给出$N$只奶牛每一只的起始地和目的地，计算Bessie最少需要的驾驶量。Bessie意识到她需要偶尔把牛放在某一个地方而不是把它送到目的地才能省油钱。
Bessie在栅栏最左端（位置0）开始工作，而且必须在最右端（位置$M$）结束她的工作。

---

思路：

显然无论怎样在中途放下牛来接另外一头牛是不会导致答案更优的。
对于每头牛的起点和终点，中间的路是肯定要走的。
接下来的问题就是当Bessie送完一头牛之后，要到另外一头牛的起点。我们要安排适当的接送顺序使得这些路程尽量小。
于是可以按照起点和终点分别排序，然后两两配对。也就是说，对于排过序的起点终点数组$a,b$，我们让Bessie到达$b_i$之后去$a_i$接下一头牛。
同时，可以把点0看成终点，点$m$看成起点一起排序。相当于从点0出发，到点$m$结束。

---

代码：

#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;const int N=100010;
int n,m,a[N],b[N];
ll ans;int main()
{scanf("%d%d",&n,&m);for (int i=1;i<=n;i++){scanf("%d%d",&a[i],&b[i]);ans+=(ll)abs(a[i]-b[i]);  //中间的距离先加上}a[++n]=m; b[n]=0;sort(a+1,a+n+1);sort(b+1,b+n+1);  //排序for (int i=1;i<=n;i++)ans+=(ll)abs(a[i]-b[i]);  //两两配对printf("%lld",ans);return 0;
}

这篇关于【JZOJ3187】的士【模拟】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---