「Codeforces 1091F」New Year and the Mallard Expedition

题目链接:Codeforces 1091F

Bob 是一只鸭子,他想去 Alice 那里,这段路程可以分为 $n$ 段,Bob 位于最左侧,Alice 位于最右侧。每一段都有一个长度 $l_i$(单位为米),还有一个地形:草、水、山。

Bob 有 $3$ 种运动类型:游泳、步行、飞行。他可以在这些类型之间任意切换,也可以在任何时间改变运动方向。Bob 只能在水上游泳,只能在草地上步行,但是在任何地形上都能飞行。飞行、游泳、步行 $1$ 米分别需要 $1,3,5$ 秒。

Bob 的能量是有限的。每游泳或步行 $1$ 米都可以增加 $1$ 个单位的能量,而每飞行 $1$ 米会消耗 $1$ 个单位的能量。起初他的能量为 $0$。

请求出他到达 Alice 所在位置的最短时间。

数据范围:$1\le n\le 10^5$,$1\le l_i\le 10^{12}$。


Solution

贪心好题啊!QAQ

我们考虑贪心地在山上飞行,在水中游泳,在草地上步行,记录下花费的时间和能量。这样的方案可能会导致两种问题:在飞行时能量不够;或者在最后剩下了一些能量。

  • 缺乏能量
    如果我们缺乏能量了,那么我们可以选择在“原地”步行或游泳来获得能量。例如,我们向后移动 $0.5$ 米,再向前移动 $0.5$ 米,就可以获得 $1$ 个能量)。为了更快的获得能量,显然这个过程要尽可能地在水上游泳完成。换言之,我们所有的能量都要尽可能在第一个水上获得;如果在缺少能量的地方之前没有水,那只能在草地上获得能量。
  • 多余能量
    如果我们在最后有多余的能量,肯定要将一些步行或游泳换成飞行。注意转化 $1$ 米的移动需要多消耗 $2$ 个单位的能量(因为不但没有得到能量还额外消耗了 $1$ 个单位的)。又因为步行的速度更慢,因此要尽可能将步行转换为飞行。这个部分的细节比较多。考虑一种情况:如果我们过早地进行转换,可能在某个地方耗尽能量。由于不能在任何一个时刻使能量变为负数,我们设当前时刻经过的草地长度为 $G$,当前能量为 $S$,那么可以转化的能量不大于 $G$,也不超过 $\frac{S}{2}$。故我们可以直接将 $G$ 更新为 $\min\left(G,\frac{S}{2}\right)$。最后我们把 $G$ 米的步行转换为飞行,把 $\frac{S}{2}-G$ 的游泳转换为飞行。

时间复杂度:$\mathcal O(n)$。


Code

#include <cstdio>
#include <algorithm>

const int N = 1e5 + 5;

int n;
long long a[N];
char s[N];

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &a[i]);
    }
    scanf("%s", s + 1);
    long long sta = 0, ans = 0, sum = 0;
    bool wat = 0;
    for (int i = 1; i <= n; i++) {
        if (s[i] == 'G') {
            sta += a[i], ans += 5 * a[i], sum += 2 * a[i];
        }
        if (s[i] == 'W') {
            sta += a[i], ans += 3 * a[i], wat = 1;
        }
        if (s[i] == 'L') {
            sta -= a[i], ans += a[i];
            if (sta < 0) {
                ans += -sta * (wat ? 3 : 5), sta = 0;
            }
        }
        sum = std::min(sum, sta);
    }
    if (sta > 0) {
        ans -= 4 * sum / 2 + 2 * (sta - sum) / 2;
    }
    printf("%lld\n", ans);
    return 0;
}

发表评论