[Solution][Greedy]USACO2013 FEB T2 Taxi

【题目】

戳这里

【题意】

奶牛Bessie在一个为[0,m]的整数区间上开出租车,任意时刻除了他自己之外只能再搭乘1只奶牛。

现在有n只奶牛等待被提供服务,他们一开始所处的位置为Si,需要到达的目标位置为Ti。

Bessie可以在任意位置将当前出租车上的乘客放在当前的位置。

Bessie的出租车开始所处的位置为0,使所有乘客到达目的地后,她需要到达位置m。

求出Bessie完成所有任务所行驶的最短长度。

【思路】

贪心。

由于出租车上只能有一名乘客,所以出租车上有乘客所需要走过的总距离为

计算完了这些,相当于可以在一位乘客的起点和终点的位置之间进行“瞬间转移”。

即到达一位乘客的终点后,放下该乘客,再去找起点位置距离该终点位置距离最短的那位乘客,让他上车,到了终点后再反复。。。

一开始从终点开始找到起点,不妨把0看作终点,m看作起点。

怎么快速找到离终点最近的下一个起点呢?

可以把起点序列和终点序列分别排序,最近起点就是起点序列中的终点在终点有序序列中位置这个位置的起点。

这样排序后扫一遍就可以了。

【代码】

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
inline int _abs(int a , int b)
{
    return a < b ? b - a : a - b;
}
const int N = 100010;
int S[N] , T[N];
int main()
{
    int n , m;
    scanf("%d%d" , &n , &m);
    LL tot = 0;
    register int i;
    for(i = 1 ; i <= n ; ++i)
    {
        scanf("%d%d" , &S[i] , &T[i]);
        tot += _abs(S[i] , T[i]);
    }
    S[++n] = m;
    T[n] = 0;
    sort(S + 1 , S + n + 1);
    sort(T + 1 , T + n + 1);
    for(i = 1 ; i <= n ; ++i)
        tot += _abs(S[i] , T[i]);
    printf("%lld" , tot);
    return 0;
}
comments powered by Disqus