【题解】Taxi G

题目描述

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

© 允许规范转载