题目描述

长度为$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

2 10 
0 9 
6 5 

输出 #1

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$ 看作起点,再进行上述匹配即可。

代码

#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
如果觉得我的文章对你有用,请随意赞赏