题目描述
长度为M的栅栏上，有N头牛需要坐车前往别的地方，起点和终点分别为s_i和t_i。现在一辆出租车从最左端0出发，要运送完所有牛，最后到达最右端M，求最小路程。出租车只能一次载一只牛。
输入格式
第1行:N和M。
第2至N 1行:第i 1行包含两个整数s_i和t_i (0 <= s_i, t_i <= M)i头牛的起始位置和目的位置。
输出格式
一行一个整数，表示出租车的最小路程。注意，结果可能超出int类型。
输入输出样例
输入 #1
代码语言：javascript复制2 10
0 9
6 5 输出 #1
代码语言：javascript复制12分析
设总路程为 sum，载人路程为 bringing，空载路程为 empty，易得 sum=bringing empty。又由 s_i 和 t_i 的定义可得，bringing=abs(s_i-t_i)，所以 sum=abs(s_i-t_i) empty。此时我们就将问题转化成了求 empty 即空载路程的最小值。
如图1，我们首先向 ans 添加 bringing 即 abs(s_i-t_i)。
然后我们利用贪心的思想来解决 empty 的问题，我们首先通过观察得到 empty 的最优解为图中的三段距离，然后我们很容易发现这是通过每个终点和离其最近的起点得到的，所以如图2，我们只需要让程序将 0 看作终点，将 m 看作起点，再进行上述匹配即可。
代码
代码语言：javascript复制#include<bits/stdc .h>
#define int long long
using namespace std;
int n,m,a[100001],b[100001],ans;
signed main(){
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;i ){
scanf("%lld%lld",&a[i],&b[i]);
ans =abs(b[i]-a[i]);
}
a[0]=m,b[0]=0;
sort(a,a 1 n);
sort(b,b 1 n);
for(int i=0;i<=n;i ){
ans =abs(b[i]-a[i]);
}
printf("%lld",ans);
return 0;
}最后修改：2021 年 07 月 20 日 03 : 12 PM
© 允许规范转载
