「BZOJ 3062」Taxi - 贪心

Bessie 在农场上为其他奶牛提供出租车服务。这些奶牛已经在沿着长度为 的栅栏上不同的地点聚集等候。不幸的是,他们已经厌倦了他们当前所在的位置并且每只奶牛都想要沿着栅栏去别的地方走走。Bessie 必须赶到这些奶牛的起始位置,并把他们带到它们的目的地。Bessie 的车很小,所以她只能一次只能搭载一头奶牛。奶牛可以在同一时刻完成上车和下车。

为了节省燃气,Bessie 想以尽可能少的燃料完成这次任务。 只奶牛的起始位置和结束为止都是已知的,请确定 Bessie 的最少行程。Bessie 意识到,要使所得到的行程最短,Bessie 可能将在沿途中让奶牛上车或下车而并不一定将一头奶牛从起点直接送到中点。

Bessie 的起点是围栏的最左端,位置记为 。终点在篱笆的最右边,位置记为

链接

BZOJ 3062

题解

表示第 头牛的起点, 表示第 头牛的终点。

首先,对于每头奶牛,一定需要将其从起点送到终点,这部份对答案的贡献固定为

每次送完一头牛后,都需要去到另一头牛的起点,即每次都要从一个 位置去到 ,考虑到在开始和结束时要从 ,即将 作为一个 作为一个

考虑如何安排可以使这个行程最短 —— 尝试将 数组和 数组分别从小到大排序,每次从 走到 一定是一组最优方案。反证法,交换 中任意两个数不会使答案更小。

代码

#include <cstdio>
#include <algorithm>

const int MAXN = 100000;

int main() {
    static int n, m, s[MAXN + 1], t[MAXN + 1];
    scanf("%d %d", &n, &m);

    long long ans = 0;
    for (int i = 1; i <= n; i++) scanf("%d %d", &s[i], &t[i]), ans += abs(s[i] - t[i]);

    s[0] = m, t[0] = 0;
    std::sort(s, s + n + 1);
    std::sort(t, t + n + 1);

    for (int i = 0; i <= n; i++) ans += abs(s[i] - t[i]);

    printf("%lld\n", ans);

    return 0;
}